11 replies to this topic

[BraXi]

Hello, I have one concept idea for rendering and I'm not sure if it's good technique and if there any better.
At initialization i made array with 4096 slots for objects that later will be rendered in 3D mode (players, monsters, props)
and to add object to screen i use:

(pseudo code)

Object *obj = spawnobject();
obj->origin = (0,0,0);
obj->modelIndex = 4; <- the model i want render
obj->show = true;
obj->deleteTime = currenttime + 3000; <- time in miliseconds

spawnobject() is searching for free slots in object array and returns pointer to object.

That way i don't need to add objects to list each time i redraw scene, which i think is faster than creating array of objects each time.

At rendering stage i do this:

for( i=0; i < max objects; i++, object++ )
{
if( !object->used )
continue;

if( object->deletetime >= current time )
{
deleteobject( object );
continue;
}

<at this stage I'm determining which object is visible and if everything is ok i render actual model at given origin>
}

To delete objects i simply memset() all values and change object->used to false to free the slot. Is this method okey? Maybe you have better ideas? I wonder if there are better methods and i would like see your feedback.

[zacaj]

What do you mean by adding objects to the list each time you redraw? Why do you delete them after 3 seconds? Are you using just C or C++ too? If you're using C++ you should just use a std::vector or something to store your objects. If you are just using C, instead of keeping a used variable per object, just keep the total number of objects you have, and when one is deleted move the last one into that space:

#define MAX_OBJECTS 4096
Object *objects=malloc(sizeof(Object)*MAXOBJECTS);
int numObjects=0;
Object *spawnObject()
{
	  return &objects[numObjects++];
}
void removeObject(int pos)
{
	 memcpy(&objects[pos],&objects[--numObjects],sizeof(Object);
}

then you can save time when drawing your objects by just stopping once you get to numObjects

Edited by zacaj, 22 September 2012 - 05:34 PM.

[BraXi]

Thanks for idea but doesn't array changing result in performance drop?

[zacaj]

What exactly do you mean by array changing?

[BraXi]

What exactly do you mean by array changing?

I mean changing item order, it could take some time if I'm right.

Edited by BraXi, 23 September 2012 - 11:35 AM.

[zacaj]

It could, yes. However I doubt it's any worse than running through 3000 empty objects every frame. Also, you could just make it an array of pointers, which would mean you'd only be doing a single assignment instead of memcpying a whole Object

[slayemin]

It's better to use a memory pool for your objects. This helps you avoid having to "new" and "delete" objects as they come and go (which costs cpu time). It also keeps your allocated objects contiguous in memory which helps with CPU caching. Instead of "new"ing an object every time you need to instantiate it, just pick a dead object and call an initialization function on it with the parameters you need to instantiate it. When you don't need the object anymore, just set its state to "dead" so that it can be reused.

As for rendering objects, each object should know how to render itself with respect to all of its states. Ideally, you should be able to loop through all of your active objects within your game and call their render function. You'll probably need to worry about the rendering order as well, so you'll want to keep your list of renderable objects sorted by their z-order so that more distant objects are rendered before nearer objects. You can get even more complicated by calculating whether or not the object is even visible before rendering it (so you don't waste time rendering offscreen objects).

[ATC]

I would opt against using a huge array ([4096]) to store objects. Not only is that wasteful but it's not a very elegant solution either. You also probably don't want to try to store objects in user-created memory unless you've written your own memory manager and you've proven (through testing) that it outperforms the C++ runtime's default memory management.

Instead you should create a data-driven rendering system which you feed render operations. Swiftcoder has made a lot of very good posts about this and is in fact the person who introduced me to the concept. Essentially, you'd want something like this:

[source lang="cpp"]// Some C++-ish pseudo-code; don't use verbatimclass RenderOp{public: Mesh* pMesh; Material* pMaterial; // add whatever else you need };class RenderOpBatch{protected: SomeCollectionType<RenderOp> renderOps;};class Renderer{public: void Draw( const RenderOp op );protected: RenderOpQueue* queue;};[/source]

That's not any sort of working implementation, but hopefully it conveys the point. You can use this to sort, batch and arrange to your heart's content. You can use collection types already found in the standard C++ libraries or you can write custom ones. For instance what I'm doing is creating a custom type called "RenderOpBatch" that allows me to batch render operations. For example, I might want to do a batch for all the parts of a rigged/skinned biped mesh and transmit information for it to the proper shaders/fragments. Batches are pushed into another custom collection type, a "BatchQueue".... however, unlike a standard queue type it allows you to select between LIFO, FIFO and custom sorting arrangements. With a little effort you can implement the same thing.

One thing is for sure: you don't want objects to be responsible for drawing themselves. This makes your engine code hideous, bloated and virtually impossible to port to or support multiple platforms. Defer that work to the renderer as described above. You can be creative in how you strip render operation data from objects, scenes/nodes, etc. Just stick to the data-driven philosophy and you will be a much happier programmer in the end.

EDIT:

Also, as someone else mentioned, do not store entire objects in memory within arrays, lists, collections, etc... Store only the pointer to it. Otherwise, you're duplicating (potentially) a LOT of data; plus, modifying one instance in one set of memory will not reflect the changes in another... and any type of sorting/moving operation requires a LOT of extra work for the CPU. Remember that the CPU moves data fastest when it comes in chunks that match the native size of the registers (e.g., 32-bit chunks for x86, 64-bit chunks for x64). So storing the pointers to objects in your array/list/collection can be a marked optimization, as pointers will naturally match the optimal native data size.

Edited by ATC, 23 September 2012 - 04:39 PM.

[BraXi]

Thanks for feedback, I'm currently using pointers in my array and ATC your idea seems to fit into my engine. I can't write too much in this post now because I'm about to go somewhere. I will reply when i test your method. Thanks again ;)

[BraXi]

Yeah it worked ;) Occasionaly there's only a little diference in performance between my <poor> method and yours.

[phantom]

Also, as someone else mentioned, do not store entire objects in memory within arrays, lists, collections, etc... Store only the pointer to it. Otherwise, you're duplicating (potentially) a LOT of data; plus, modifying one instance in one set of memory will not reflect the changes in another... and any type of sorting/moving operation requires a LOT of extra work for the CPU. Remember that the CPU moves data fastest when it comes in chunks that match the native size of the registers (e.g., 32-bit chunks for x86, 64-bit chunks for x64). So storing the pointers to objects in your array/list/collection can be a marked optimization, as pointers will naturally match the optimal native data size.

However you have to becareful with this kind of thinking.

Pointers are basically cache miss factories and missing the cache is one of the worst things you can do as the CPU has to stall while it goes off to fetch data from memory. Amusingly as CPUs have gotten faster that stall has gotten worse as it can take hundreds of cycles before your data has been fetched which is all time the CPU is left twiddling its thumbs.

For certain operations it is BETTER to pack memory into contiguous chunks and access them in one direction from start to end; the pre-fetcher in the CPU will hide some to all of the latency of memory fetches and you'll be basically pulling data from cache as you go. Of course you also have to pay attention to data layout but it can be worth it.

So, if I was writing a command list system for feeding a graphics API would I embed the mesh into the list? No.
But would I embed the translation matrix? Yes, I would as I'm going to want to get that and going via a pointer is just accessing memory for the sake of accessing memory.

Data layout and cache friendlyness are two of the most important concepts going; saving some bytes by using a pointer instead of a real object might seem clever but often it can result is slowing things down rather than speeding it up.

Learn how the system works and avoid "typical C++ bullshit" (google that, it's a good read) if you want to do things quickly.

[demonkoryu]

And read Pitfalls of Object Oriented Programming, while you're at it.