Sign in to follow this  
xDan

using classes and vectors in a 3D engine

Recommended Posts

xDan    194
Can anyone tell me... are classes and vectors suitable to be used (lots) in a 3D engine? They make things so easy, I feel suspicious that they might be slow or something. Ideally I would like to create some massive object oriented monstrocity. With say, one main world class. In this I would have vectors of other classes such as models, meshes, cameras etc. All would have their own constructors and deconstructors. Even the mesh classes would contain vectors of polygons, not arrays. The polygons would have vectors of vertices even! And it would all have to be looped through in the rendering routines. So... Before I start writing this, I need some advice. Are vectors suitable in such speed intensive loops? Are classes good? Should I restrain myself from putting everything as a class? My main render would be something like:
for main.meshes.size()
	for mesh.polygons.size()
		for mesh.vertices.size()
			draw_polygon
(maybe I should figure out a way of having all polygons in one array. :-/ ) I could always go back to C using good old malloc. I hope I explained myself clearly.

Share this post


Link to post
Share on other sites
dave    2187
Since CPUs are so damned fast these days the slight overhead that STL has is even more negligable. The same goes for the overhead of C++ compared to C.

This said, it is more down to the programmers alogrithms that determine the speed and efficiency at which an app/game will run. Just remember to inline things, that will speed things up.

ace

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by xDan
Can anyone tell me... are classes and vectors suitable to be used (lots) in a 3D engine? They make things so easy, I feel suspicious that they might be slow or something.


Never make assumptions on things you on things you don't not yet understand.

In C++ you only pay for what you use. Saying classes are or might be slow is nonsenical, you need to be abit more specific. for one there can be different kinds of classes that result in differnt kind of user-defined types, like value types, polymorphic types etc, each with varying tradeoffs.

Same goes with std::vector exactly what aspect are referring to, in general on modern C++ compilers std::vector is very very efficient. When optimizations are on std::vector is equivalent in efficiency to a C-style dynamic array, in some cases it can be more efficent because of naive use of C-style dynamic arrays. Not only that it handles memory managemnet for you, it has alot more functionality, you can provide custom allocators types to it.

Of-course naive use of std::vector can result in less efficient use but that is just the same with anything you do not just std::vector.

At the end of the day it all depends on how your using it.

Quote:
Original post by xDan
Ideally I would like to create some massive object oriented monstrocity. With say, one main world class.


I think OO is way to overrated [grin], its just a tool, don't go nuts about it.

Quote:
Original post by xDan
Are vectors suitable in such speed intensive loops?


Again it depends on how you use it, exactly what do you mean, allocating memory, growing? accessing elements? need to be more specific.

Quote:
Original post by xDan
Are classes good? Should I restrain myself from putting everything as a class?


Again it all depends, don't just do it for the sake of following a crowd and being OO. C++ is actually a multi-paradigm language you will probably use a bit of everything.

Quote:
Original post by xDan
I could always go back to C using good old malloc.


The problem is generally you should never use C memory functions on non POD-types (plain old data type, a technical term used in the standard) directly, they deal with uninitialized memory if you do use them then you'll need to use some advance C++, placement new operator, explicitly invoking destructors etc, etc, its not normal code.

It is good to separate the concept of allocation/deallocation and construction/destruction for efficency reasons in some contexts and its what the standard library containers like std::vector do with the allocator type, but its advance C++ and much to low-level to use in normal every-day code thats why you should prefer std::vector over C-style dynamic arrays in C++.

[Edited by - snk_kid on June 4, 2005 9:41:12 AM]

Share this post


Link to post
Share on other sites
Oxyacetylene    426
I don't see a problem with object oriented engines, I'd say go for it, however...

Quote:
Original post by xDan
The polygons would have vectors of vertices even! And it would all have to be looped through in the rendering routines.
.


That sounds like overkill to me, to be honest, especially if all your polygons are just going to be triangles. I agree with your other uses of vector, but that's where I draw the linie.

One criticism I've heard of STL, from professional programmers, is that newer programmers tend to go overboard with it, and use it in places where a regular array would be sufficient.

Personally I don't agree with the, always use vector instead of array strategy. Sure, if it's an array that's being dynamically allocated, go for a vector, but if youre just using an array in a function, and you know it will always be of some fixed size, just go for a regular array.

For example, in my current project, I loop through a small array of DirectX depth/stencil formats, checking each one to see if it's supported. I could have used a vector in this function, (and incidently, I did the last time I wrote this function, two years ago!) but to me, that would be overkill, and completely pointless.


//Depth stencil formats to search for, in order most preferred first
const D3DFORMAT formats[] =
{
D3DFMT_D24S8,
D3DFMT_D24X4S4,
D3DFMT_D15S1,
D3DFMT_D32,
D3DFMT_D16
};

UInt formatCount = sizeof(formats) / sizeof(D3DFORMAT);
HRESULT result = 0;

for ( UInt index=0; index < formatCount; ++index )
{
... check for format support here
}




Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Oxyacetylene
Quote:
Original post by xDan
The polygons would have vectors of vertices even! And it would all have to be looped through in the rendering routines.
.


That sounds like overkill to me, to be honest, especially if all your polygons are just going to be triangles. I agree with your other uses of vector, but that's where I draw the linie.


Exactly why is that overkill? if you do not know the size of the array at compile-time then your either gonna have a C-style dynamic array or std::vector of vertices and as every well respected person in the industry (such as Herb Sutter), moderators of gamedev.net forums, and other posters here keep going and on and on, you should be using std::vector over C-style dynamic arrays in C++.

Quote:
Original post by Oxyacetylene
One criticism I've heard of STL, from professional programmers, is that newer programmers tend to go overboard with it, and use it in places where a regular array would be sufficient.


Some of those people that say that also don't know how to use the standard library effectively them selfs, some of them are those people that because they don't know how to use effectively get the complete wrong idea and end up re-inventing the wheel with a flat tire because they have little to no clue as to whats involved.

I'm not saying standard library is perfect of-course, and not all data structures & algorithms in existence are available in the standard library.

I also think the wright abstraction should be a higher/first priority than efficency and/or going overboard.

Quote:
Original post by Oxyacetylene
Personally I don't agree with the, always use vector instead of array strategy. Sure, if it's an array that's being dynamically allocated, go for a vector, but if youre just using an array in a function, and you know it will always be of some fixed size, just go for a regular array.


Agreed but everyone who suggests that have never said to use it as a replacement for a statically allocated arrays, if you have read some of my posts similar to this context i always suggest using std::vector over a C-style dynamic array, never a statically allocated one.

Share this post


Link to post
Share on other sites
Oxyacetylene    426
Quote:
Original post by snk_kid
Exactly why is that overkill? if you do not know the size of the array at compile-time then your either gonna have a C-style dynamic array or std::vector of vertices and as every well respected person in the industry (such as Herb Sutter), moderators of gamedev.net forums, and other posters here keep going and on and on, you should be using std::vector over C-style dynamic arrays in C++.


Well, OK, correct me if I'm wrong on this, and I will admit right here that using a std::vector is an acceptable solution. But, in a 3D engine, it's my understanding that all the "polygons" you will draw are going to be triangles, right? In the future, they're still going to be triangles, due to the inherent advantages triangles have?

Then what's the point in using a vector, when you could just use a static array of points?

It's not so much that vector is a hugely unacceptable solution, it just seems like overkill, with no real benefit, other than the convenience of being able to use begin(), and end().

Quote:
Original post by snk_kid
Some of those people that say that also don't know how to use the standard library effectively them selfs, some of them are those people that because they don't know how to use effectively get the complete wrong idea and end up re-inventing the wheel with a flat tire because they have little to no clue as to whats involved.


I'm talking about, for example, the situation I outlined in my example code.
You would gain absolutely nothing from using a vector in that situation, yet some newer programmers would use a vector because they think that arrays are always evil and unsafe.

I'm not 100% sure, but I think the programmers were complaining about newer programmers using vectors where a static array would have been just fine.

I use vector, and other STL containers extensively in my own projects, I like safe structures that clean up after themselves, like smart pointers. I don't believe you can always trust the programmer to call delete, or Release, especially when you take exceptions into account.

Share this post


Link to post
Share on other sites
Monder    993
Note that looping through all the verticies in a model and drawing each polygon individually will be horrifically slow. Though you can still store the verticies in a vector. You could write a VertexBuffer class which would be responsible for storing vertex arrays and drawing them etc.

Share this post


Link to post
Share on other sites
mrbastard    1577
Quote:
Original post by Monder
Note that looping through all the verticies in a model and drawing each polygon individually will be horrifically slow.


He might be writing a software renderer. You're obviously right otherwise though.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Oxyacetylene
Quote:
Original post by snk_kid
Exactly why is that overkill? if you do not know the size of the array at compile-time then your either gonna have a C-style dynamic array or std::vector of vertices and as every well respected person in the industry (such as Herb Sutter), moderators of gamedev.net forums, and other posters here keep going and on and on, you should be using std::vector over C-style dynamic arrays in C++.


Well, OK, correct me if I'm wrong on this, and I will admit right here that using a std::vector is an acceptable solution. But, in a 3D engine, it's my understanding that all the "polygons" you will draw are going to be triangles, right? In the future, they're still going to be triangles, due to the inherent advantages triangles have?

Then what's the point in using a vector, when you could just use a static array of points?

It's not so much that vector is a hugely unacceptable solution, it just seems like overkill, with no real benefit, other than the convenience of being able to use begin(), and end().


Sure if you can have a statically allocated array of points then i would also say there is no point in using std::vector and you can still use C-style arrays with STL algorithms they don't need a begin/end method arrays come with iterators built in they are pointers [grin].

Anyways that is hardly the case as vertices are typically read from number of files where the number of vertices is typically unknown at compile-time.

Going slightly off topic for a second, some of the main advantages of std::vector over a typical C-style dynamic array in this context is that:

1. std::vector separates allocation/deallocation and construction/destruction, this allows you to not only store user-defined types with-out default constructors, it also allows you to first allocate a chunk of uninitialized memory and then incrementally initialize each element if wish too. You can do this in C++ with C-style dynamic arrays but its un-normal very low-level advance C++ code that is prone to error, std::vector takes care of this aspect for you via the help of the allocator concept and allocator types.

2. Not a typical operation in this context but growing, when growing an array std::vector is typically implementated using an exponential growth strategy known to give good all round performance. When std::vector has reached its full-capacity it exponentially grows some more uninitialized elements for later. Most people would probably grow the array by one element which is naive.

Now consider an example where somebody is going to read in vertices from a text file,

the naive approach would be:


std::ifstream ifs("...");

size_t num_of_elements = 0;

ifs >> num_of_elements;

vector3* verts = new vector3[num_of_elements];

std::copy(std::istream_iteartor<vector3>(ifs),
std::istream_iteartor<vector3>(),
verts);

//....
delete[] verts;


You might be wondering why is this navie? well because when you create an array this way using array new implicitly, all elements are default constructed that costs time and is redundant. Why can't we just allocate uninitialized memory and initialize elements as soon as we read the values in? well we can and its simple with std::vector:


typedef std::vector<vector3> vecs;

std::ifstream ifs("...");

vecs::size_type num_of_elements = 0;

ifs >> num_of_elements;

vecs verts;

v.reserve(num_of_elements); // allocates a chunk of uninitialized memory

std::copy(std::istream_iteartor<vector3>(ifs),
std::istream_iteartor<vector3>(),
std::back_inserter(verts));


heck we can even change the code simply to:


std::ifstream ifs("...");

std::vector<vector3> verts((std::istream_iteartor<vector3>(ifs)),
std::istream_iteartor<vector3>());


You can do this with C-style dynamic arrays but the code is very low-level and undersirable, e.g.


std::ifstream ifs("...");

size_t num_of_elements = 0;

ifs >> num_of_elements;

// allocates memory only.
vector3* verts = static_cast<vector3*>(::operator new(sizeof(vector3) * num_of_elements));


// constructs memory only
// (uses placement new operator internally to do in-place construction)
verts = std::uninitialized_copy(std::istream_iteartor<vector3>(ifs),
std::istream_iteartor<vector3>(),
verts);

// ....

// we are finished now, destroys memory only
for(int i = 0; i < num_of_elements; ++i)
verts[i].~vector3(); // you must do this for user-defined types
// when using placement new.

// deallocate memory only
::operator delete(verts);


Nobody is going to (or want to) generally code at that low-level. You could skip destruction of elements if the user-defined type has trivial destructor but only you can know that. Why bother with all that when std::vector takes care of it for you.

Another reason to use std::vector over a C-style dynamic array is to implement some form of Resource Acquisition Is Initialization (RAII)

[Edited by - snk_kid on June 4, 2005 3:12:49 PM]

Share this post


Link to post
Share on other sites
xDan    194
That's a scary amount of posts... :D

Thanks all for your help. So the speed is proportional to the skill of the programmer. I'll use classes and vectors then, as there seems to be no problem.
As for using vectors for the vertices, I should be okay with a normal array.

Quote:
You could write a VertexBuffer class which would be responsible for storing vertex arrays and drawing them etc.

Vertex buffers. I've heard of them but not used them myself. Although I did have some idea that they wouldn't be suitable for animated models - if the vertices positions were changing often. I guess it's something I need to learn.

I can't see how my *new* engine will be slower than my last (software rendered... :-( ), so i'll probably end up happy. ;)

Share this post


Link to post
Share on other sites
chad_420    290
I always assume that code I wrote is the slowest part of my app. I have never been wrong about that yet. Also optimisaton comes last not first. Get your shit working before ya try to make it faster you know! Optimising code you havent written is like putting a turbo charger in a car without wheels!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this