#Is my code easy to read for potential collaboration?

1 messages · Page 1 of 1 (latest)

copper axle
#

Common engines project 3D space into 2D space
But that usually makes the original data (object instances, 3D coordinates) inaccessible
And you will be stuck infering it from flattened data, very cumbersome to do, and might require a lot more fetching.

The Hollows does the opposite, I projects pixels to world space,and gives them access to direct world data.

But for that to work, we need:

  • a "smart" world that is VERY fast to access and iterate through, that also supports LOD "searching"
    This is called "bitfield", and it's a 3D mipmap of the world, where it only stores bits that tell "are there objects here or not"
    The bitfield has an identical map, but this one includes actual references to objects based on coordinates
  • objects that update their coverage in space, and only do so on movement (fill their bitfields and references in all relevant cells)
  • bitfields and cells CAN be nested, but bitfields are where the search happens, and these must fit into L1 cache each (one bitfield with its mips should not exceed 4 kb, an identical field will be used for transparency detection)
  • a PrePass that takes the camera location, and searches the world bitfields, to early out and catch refs of objects in the way, this can go down to pixel level through 3-4 nested bitfields, some care needs to go to parallelism here since it will not be straighforward.

And most importantly: this system will NOT rasterize or use polygons/triangles to render.
Instead, it will utilize DataPoints in space, and interpolate between them.

DataPoints must have normals, and can include:

  • vertices
  • texture pixels
  • particles
  • lights

And so on..
Basically: if it exists in 3D space, it's a datapoint
It signs itself up to relevant bitfields, and removes itself accordingly.

The highest level of available data will be used for rendering (often that is texture pixels)

And each cell has its own pre-baked "average" data, to avoid going down the details when not needed

#

Now since updating an entire world down to the pixel is.. near impossible, we have 2 separate levels of "data retrieval"
One is world space, the other is local
Local data is pre-baked per object and rarely updated (unless the entire object changes shape down to the detail)
Local is also used between texture pixels and vertices (if we coul'd utilize UVs for that)
Only a transform is used to multiply local data, instead fo rebuilding the entire dataset

Local data can also be instanced

  • The prepass goes through all the data, and maps out the references to a 2D grid that civers 1 pixel per grid cell, then each pixel would retrieve it's own 3D data once, while assuming its position in 3D space (this will be utilized for lighting calcs and such later)
sly field
#

what do the all-caps filed names mean? normally all-caps is used for constants in odin

copper axle
#

I just noticed your username, it's cool

sly field
#

thank u!

#

i don't quite get how the position of a vertex relates to it's position in the cells?

copper axle
#

For the smallest cells (highest level) each cell = 1 cubic meter

#

The objects sub themselves to all the cells they fill
And you can get which objects when you go through the bitfield anf find which are occupied

#

You check the same location in the ref array (let's call it datafield) and forward any data refs needed

sly field
#

in cpu_fragment_shader once u get the vertex from the cells u use vertex.pos when rendering to the screen, that's what confuses me

#

does it currently display anything in 3D, it seems like rn it justs displays a 2d slice exactly at the camera

copper axle
#

Are you on the dev branch?

#

Check calcs and the bitfield functions

#

Cells..etc

copper axle
sly field
copper axle
#

I have some images in the debug

copper axle
#

The main branch keeps the last "visual" version

sly field
#

im on dev now, but the shader is commented out so it produces nothing

#

also there's not much point having separate main and dev branches at this point since they're both unstable, the only difference is that main is out of date and that doesn't seem terribly useful

sly field
copper axle
#

Dev is between visual results

copper axle
sly field
copper axle
copper axle
sly field
# copper axle And do these make sense?

i don't understand the refs, currently they spray out in a way which has nothing to do with where they're visible from (to the best of my understanding they're supposed to tell u what the closest object in the view direction is from a cell)?

copper axle
#

The engine uses the bitfield to find the closest cells with data (bitfield only has a yes/no)

#

Then it fetches the object IDs from the cells with data

#

^ from the other identical list, or datafield

sly field
#

in cpu_fragment_shader (currently commented-out) there's a bug where u only check whether the cell index is with cells but don't check the xyz components, so if the x or y is too big it will wrap around, it's a rly easy mistake to make when going from an array of arrays to a single array

copper axle
sly field
copper axle
#

I forgot which one you are talking about, but I do remember a bunch of issues with the old code

#

Mostly trying to grab specific data

#

It lead to rethinkinthe entire approach to bitfields

#

You can assume the commented code is depracated/irrelivant

sly field
#

why is WORLD_SIZE deprecated ?

copper axle
#

I left the old one so I can still have a "fallback" code till the new one is functional

copper axle
sly field
#

calc.odin:level_offset is wrong, it gives the offset for the level one higher than level

#

instead of for i in 0 ..< level it should be for i in 0 ..< max(0, level - 1)

#

model_bitfield_get seems confused, it call xyz_to_index with each level for the same x, y, z but xyz_to_index expects the inputs to be centered on some level, clearly the same xyz can't be centered on every level

copper axle
#

Why can't it be centered?

#

Level = LOD here

#

Not shifted coordinates

copper axle
#

Easier to read

sly field
# copper axle Why can't it be centered?

if u call this with the same coordinates but different levels then the part at // Uncenter makes no sense, the corrdinate systems for the levels are [1, 1], [2, 2], [4, 4] etc. so a coordinate like (0, 1) means a different place in each of them

// Reverse: 3D coordinates to index
xyz_to_index :: proc(x, y, z: int, level: int) -> int {
    grid_size := 1 << uint(level)
    half := grid_size / 2

    // Uncenter
    x := x + half
    y := y + half
    z := z + half

    return z * grid_size * grid_size + y * grid_size + x
}
#

at higher and higher levels the coordinates will appear smooshed towards the center

copper axle
copper axle
#

😵‍💫

#

Hmm...
I'll need to dissect this bit by bit

#

I asked AI for help here

#

I usually ask it for a basic implementation then I fix it

#

Ok so..
Each level is x8 of the previous one

And x2 per axis

#

Meaning the highest level is 1 meter
The one lower is 2
Then 4
Then 8

#

Meters per axis per cell

#

The lowest level covers ALL the cells with only one cell

#

Where did I mess that logic up?@sly field

copper axle
copper axle
#

Or something

sly field
#

consider:

for x in 0..<8 {
  for y in 0..<8 {
    for z in 0..<8 {
      for level in 0..<8 {
        index := xyz_to_index(x, y, z, level)
        cell_set(bitfield, level, index)
      }
    }
  }
}

this will always produce a centered 8x8x8 cube at any level so
at level 10 (1024) this will produce a tiny cube at the center, at level 4 (16) it will produce a large cube at the center, at level 3 (8) it will produce cube that fills the whole world, and at any lower level it will overflow the bounds

copper axle
#

Gimme a bit

copper axle
#

Before I forget, thanks for dissecting my code that far

sly field
#

you might want to try that again

sly field
copper axle
#

Nvm the verison online is correct

sly field
copper axle
#

But I'm using model bounds

copper axle
#

I want the function to get the cell that has the XYZ I need
On any level

#

They're all in world space for now

sly field
copper axle
#

If we're going by axis individually, it's x2
And if we're going by the cell index, iy's not even because it contains all levels

#

Hmm...

sly field
#

your right, it should be coordinate /= 2

copper axle
sly field
#

btw world_set_at_level does work correctly

#

so u should probably just use that

#

like, it does basically the same thing as my psuedocode

copper axle
#

Like the current implementation is the basic one

#

But setting alone isnt enough, need it to unset later too, and only unset the entire upper level when the lower one has none

#

The world set at level confused me

#

So I split it to smaller functions to be able to focus

sly field
#

do u intend to use the bitfields for casting rays?

copper axle
# sly field do u intend to use the bitfields for casting rays?

Not sure how much my approach fits traditional raycasting, but the basic plan:

Define camera field of view in the 3D world (the bounds)

Go over the cells (then their sub cells by level) and grab the closest, level by level, till you reach the max level, then grab the refs from the identical cells in the datafield

#

Step through them basically, but filtered by LOD

#

The bitfield needs to be low to fit in L1 cache, so iterating can be fast enough

#

(There will be nesting down to the texture pixel level so yeah, but from the 1 meter mark, ut goes though object instances with local bitfields)

sly field
copper axle
#

A 2D grid should be created and filtered down, based on what each object covers

#

The 2D grid will be: 1 cell = 1 pixel

sly field
# copper axle As many as needed to cover all the potential pixels from the camera

so lets say there's at least one thing in all four corners of the world, so at level 1 every cell is occupied, and for some pixel on the screen i search for what the corresponding line of vision would hit; wouldn't the level 1 cell i'm in always say it's got what i'm looking for, even if i have a clear line into another cell?

#

BVH's handle that case keeping track of a ray and at the lowest level doing an actual collision detection

copper axle
copper axle
sly field
copper axle
#

But the bitfield needs to remain lean for quick access

#

Like to fit in L1 cache

#

Both should use the same structure so it's easy to catch the exact same cell

sly field
copper axle
#

but the datafield is too large compared to bitfield

#

so you use bitfield for detection and datafield for grabbing refs

sly field
# copper axle exactly

wouldn't the datafield have to be recalculated every frame while the camera is moving?

copper axle
#

this system isn't raster, it's kinda the reverse
camera pixels project themselves to the 3D space

#

but more accurate to say, the prepass maps their 3D postion based the bitfield, then forwards the ref to the relevant data and 3D coords

sly field
copper axle
#

Just calc the distances

sly field
copper axle
#

The idea from the system is to always have spatial awareness

copper axle
#

The coordinates don't change when the camera moves

#

Only the cam coordinates change

sly field
# copper axle Yes, in WORLD space

but the world space coordinate of the object u should have hit is, perhaps counterintuitively, still dependant on the angle the ray approaches from

#

it's specified in world space but still dependent on the camera position

copper axle
#

So lemme try to explain the workflow

#
  • define camera coordinates and angle
  • define borders based on distance
  • go over every cell on each level (down to their sub cells), if it's within camera bounds: grab it, get the model refs inside, the go over all the pixels the model covers, and "mark them off"
  • proceed to the next pixel that was not covered, repeat detection
#

It has some brut forcing (go over each cell from xyz to xyz)
But it is limited to occupied cells, which are "mipmapped"

#

@sly field does that explain it?

sly field
copper axle
#

And I want the bitfield separate so that even if I need to check each, it still would be fast cuz L1 cache

sly field
copper axle
#

Unless every single pixel had an entirely different "data point"

#

But this is one time over in the pre-pass

#

And skipping should be easy enough, but I mean even if I wasn't critical about skipping, the system is lean enough by default

#

I could be wrong tho, until it's tested, nothing is guarenteed

#

I'd just like to think that everything has a solution

sly field
#

how are u going to relate coarser camera levels to finer ones, are they each going to be exactly half the size like the levels, or are u going to continously map them? i feel like only the latter would work

copper axle
#

Wait, what camera levels we talking about here?

#

Just to note, everything here happens in world space

#

Even texture pixels have a world space coordinate (defined by the displacement map and normal map(

sly field
#

by "camera levels" i mean slices of the cameras cone, with coarser ones being closer to the eye

copper axle
#

Basiaclly you traverse the nested bitfields down to pixel level

copper axle
#

You ARE already going over each cell, just check the distance from the camera and if it's in the cone

#

The cells cover every single object in the world

#

And you grab everything close to the cam coordinates, until they fill the screen

#

You don't need to filter by cone slices

sly field
#

so u iterate over the entire world each frame?

#

until u fill the screen

copper axle
#

For the first level maybe yes, but then you filter down

#

And go further in coordinates

#

You have the cell coordinates and you can go close to far based on them

sly field
#

what does "until u fill the screen" mean, don't u need to go until not only is the screen full but each pixel is filled with the closest thing in specific?

copper axle
copper axle
#

You can grab any object ref at any time, and check what cells it covers, and early them out, down to the pixel if you want

#

You can also go up and down in levels, and go back to the levels from checking the model

#

Making this work in paralel is tricky but possible

#

Would be a little more complicated than "all models firts then all pixels" tho

copper axle
#

So if you have something with a nested bitfield, better delegate the search right on nesting

sly field
#

so a ref to an object at a point just means that the object fills in that point ?

copper axle
#

I did not plan parallelism yet, because it will rely on making the bitfields work

copper axle
#

There is another "accompanying" bitfield for transparency too, for "is something transparent here"

#

The ref CAN be for anothe4 bitfield BTW (that's how nesting would work)

#

"DataPoint" is a struct, has an enum for type
Based on the type you can deal with it properly

sly field
#

i just don't see how this scheme can get the correct depth/transparency without any explicit raycasting or draw order

copper axle
#

After checking if there is an object, check if there is transparency

#

This goes down to texture pixel level

copper axle
sly field
copper axle
#

That's how you remove or mark off screem pixels

#

I don't think we have a smaller "potentially in front" data point

sly field
copper axle
#

If you mean at texture pixel level, yes it stops there

sly field
#

is there any more code for this beyond what's in testing/calc.odin

copper axle
#

*rn no

#

There's only the commented off prepass in core loop

#

But it's empty

sly field
#

could u show me some high-level psuedocode for rendering a single frame to help me understand?

copper axle
#

Lemme tru

#

Keep in mind that it's R&D so some exact methods are up for testing, but mostly doable

copper axle
# 
Screen_Grid[] : int //referemces are IDs, so int works fine, this is the size of screen res, and each holds a ref to the datapoint in world space


Bitfield_calculate (cells: bitfield_cells) {
Cone: = camera_cone_check (data.cam.coords)
Range:= cell_range_check(cone)  //variable type that holds xyz ranges

For i in levels_count(cells)
   For cell in Range
     If cell {
        If cell_cone_distance(cell_to_xyz(cell), cone)  <  Range_xyz_to_distance(cell_to_xyz(cell), cone)
        Shrink_Range(range, cell)
        // might be better to checkt he transparent bitfield here, I mistakenly used "cells" instead of more accurate "bitfield_cells"
       // we can either call other functions here, or store a list of cell IDs/coordinates to use later, we can use either to fetch data, but let's assume IDs for now
          Append(cell_IDs,cell)
       }
     }
} 

For cell_ID in cell_IDs {
  Data_point : = Data.fields.Datafield[cell_ID]
  



 Switch Data_point.type: // idk how this is done in Odin
   Bitfield:
        Bitfield_calulate (Data_point.bitfield)
   Object:
        Object_bitfield_calulate(Data_point.bitfield)
   Vertex:
        // same but get the texture pixels bitfield, this comes nested down object bitfields
// whatever other datapoints we have

    T_Pixel: //texture pixel, max level
        Grid_ref_add_and_mark_out(Screen_Grid[], data.screen_grid_final[]) //basiaclly removes the grid cells that are covered by the pixel, to stop recalculating them, and populate their references in the final grid

// the pixel pass is rn the max level of detail, but ideally, we should be able to early out before, at object level, and at cells that are full occupied by large objects, this data can be gotten from ref > datapoint > cell coverage (of sort)

}
#

@sly field I hope this explains it a bit

#

Pretty sure that's not the best way to code it, but should give an idea

sly field
#

hwo come Range_xyz_to_distance doesn't accept range?

#

also the i in for i in levels_count(cells) is never used

copper axle
copper axle
#

My normal state is diziness, sometimes I fail to keep my focus up, sorry

copper axle
#

Let me know if you have any feedback on that @sly field

sly field
#

whats the difference between object_bitfield_calculate and bitfield_calculate ?

sly field
#

is Range like a depth buffer?

sly field
#

let me know if i'm on the right track

#

i'm not doing any mipmapping in my version and keeping the resolution very low, i just want to see soe 3d stuff correctly rendered on the screen

copper axle
copper axle
#

Lemme clone and test it

# 
object_create :: proc(s: ^State, pos: [3]int, dimensions: [3]int) -> Object_ID {
    size := dimensions.x * dimensions.y * dimensions.z
    bit_array := ba.Bit_Array{}
    ba.init(&bit_array, size)

    append(&s.objects, Object{
        pos = pos,
        dim = dimensions,
        bit_array = bit_array,
        pixels = make([]Color, size)
    })

    return Object_ID(len(s.objects) - 1)
}

mostly correct (what I am doing rn) but ideally we only want the cells that have geometry to be marked, not the full bounding box (future implementation)

# 
object_add_pixel :: proc(s: ^State, id: Object_ID, pos: [3]int, color: Color) {
    o := &s.objects[id]

    object_index := pos_2_index(pos, o.dim)
    ba.set(&o.bit_array, object_index)
    o.pixels[object_index] = color

    world_pos := pos + o.pos
    world_index := pos_2_index(world_pos, s.dim)
    ba.set(&s.bit_array, world_index)
    s.object_refs[world_index] = id
}

this adds pixels to the object's local bit array?

#

hmm.. what's pos2 index exactly?

#

around 40 FPS

image.png
#

similar FPS if I replace the function with the red color

image.png
# 
    px_size := 100
    for x in 0..<WIDTH/px_size {
        for y in 0..<HEIGHT/px_size {
            color := rl.RED//state_lookup(s, {7+x, 7+y, 7})
            rl.DrawRectangle(i32(x*px_size), i32(y*px_size), i32(px_size), i32(px_size), color)
        }
    }
#

seems like the performance is light for your test

copper axle
#

sounds about right

#

yes that logic is exactly what I am working on

sly field
#

im going for a walk, be back later

copper axle
#

a few differences in a game engine:

  • world size is larger, texture resolution is higher (which means nested bitfields are a likely requirement for both)
  • we do actually grab verts, tho I'm not sure we will need them in real-time (I'm thinking yes in the case of animated textures)
    but we grab them to get the pixels from the UV coordinates (this is up to R&D, if I can make the system figure out treasparency without baking, from UVs, that would be ideal)
  • we process more than 1 object, and we remove the entire list of screen pixels covered by each, so we don't have to process them twice
copper axle
copper axle
sly field
copper axle
#

This is fine because it only happens when the object moves

#

We can afford some fetching

#

And the lowest world cell size is 1 cubic meter rn

Unless you are moving an entire skyscraper, you often updat one or two bitfields, the object bitfields are local and don't need rebuilding

#

Ofc, this is all still in theory till we test it out

#

(And if you are interested in contributing, I am looking for collaborators)

sly field
#

that does seem like a disadvantage of this system though, because that's not the case for other forms of rendering

copper axle
#

The system should still be x100-x1000 faster than raster by default

#

And you render millions of pixels every frame, it can tank that

Updating a few thousand fields per frame is trivial in comparison

#

More optimization can be done too, all the data is mipmapped
But I'm trying to not go far before actually testin

#

(You updated all the pixels live in your test on the CPU, and it didn't even flinch)

#

BTW, if you mean disadvantage like when the world moves but the character doesn't

You can actually move the bitfield with the world, the mapping remains the same

#

Bitfield mapping is relative, but is used for the world 0,0,0 by default

sly field
copper axle
copper axle
sly field
#

also it doesn't do any mipmapping and thus no reference counting

copper axle
copper axle
#

Like 4 max per chunk

#

64 per bitfield if it has nested ones

#

Both ways yeah you're right, it needs full implementation to be sure

#

Think we can work on that together?

sly field
#

that's what that technique is generally called

copper axle
copper axle
copper axle
#

You'd need the entire world to be moving, at a distance further than a km, with a lot of large objects, and that's probably how you will get mills of calcs per frame

#

But most objects are within a couple cells max

#

So physics games might struggle here but other engines also struggle with that

sly field
#

what problem was this originally trying to solve?

copper axle
#

And if you have a beefy machine, the hardware power would be invested in what I call "visual physics" (clothes, hair..etc) that woul ideally be calculated on the GPU

#

And/Or higher resolution/framerate natively

sly field
#

when do the pixels actually get drawn to the screen, rn the only thing i can think of is to iterate every point in the world (posssibly accellerated by mipmapping), find the screen pixel, if any, that corresponds to that point and draw it to the screen with depth buffering, but the same point could map to multiple screen pixels so maybe u have to draw a whole rectangle for it and that seems infeasible, am i missing something?

copper axle
# sly field when do the pixels actually get drawn to the screen, rn the only thing i can thi...

There is a "prepass" that checks each object it finds close, then removes the pixels it covers (those can be mathematically calculated from camera position, FOV and direction)

Basiaclly we creat a 2D grid, and the prepass searches, and removes all the covered pixels, one object at a time, until there is none left

(It also skips the coordinates check to the next "none-covered" pixel, and stores the refs in another 2D grid

We probably will need another pass on th eprepass after calculating the textures iteration, because the bounds after that might differ, but we only check the pixels left uncovered
Proccess them down to pixel, and repeat prepass again if needed, till no pixels are out

The pixels then instantly access their ref list from the saved grid, based on their location on screen, and use that to assume their 3D coordinates, and begin shading

#

This is what I have in mind rn

sly field
#

when we remove/mark-off pixels, do we already now which point in 3D space the pixel corresponds to from some previous projection pass?