🔒 Locked

Object Oriented algorithm design

Started by AndyGeers Feb 24, 2007 at 3:51 AM 7 replies 1.7k views

Original Post

Feb 24, 2007 at 3:51 AM

I've been working on implementing a cloud simulation recently, and have come up again the same wall I seem to hit every time I use C++ to implement these things - it's really hard to make a clean implementation using an object oriented design. I'll tell you why I think it is: efficiency dictates that any algorithm worth its salt will invariably take advantage of the known properties of the application that you will use it for (e.g. you can take certain shortcuts knowing that X will rarely happen, or that Y will virtually always be true). Take marching cubes, for example - you can massively speed it up if you know that your scalar field is generated purely by a set of soft objects (metaballs, etc.) by starting to sample on each object's boundary and tracing the contours. But it seems to me very hard to implement something like that without constantly breaking encapsulation, etc. I could have a generic "Field" class that is inherited by "BlobbyField", but then MarchCubes(Field* pField) can't really take advantage of the blobbiness of the field. Anyway, please don't get bogged down by that example. My real question is this: In the general case, how do you go about designing a nice, clean, object oriented algorithm implementation, whilst simultaneously making it possible to take advantage of the specific application that you intend to deploy your algorithm in? How can I help myself share my code with other projects in which you can't make the same assumptions? Or do I have to accept the fact that I'm going to have to write a MarchBlobbyCubes(BlobbyField* pField) which is going to look totally different to the standard MarchCubes function?

technomancer

Feb 24, 2007 at 5:25 AM

sorry to sound confused but isn't the problem your describing solved simply with Function Overloading ? i.e you implement both the MarchCubes(Field* pField) and a MarchCubes(BlobbyField* pBlobbyField) functions ?

AndyGeers

Author

AndyGeers

Feb 24, 2007 at 6:25 AM

Quote:
Original post by technomancer
sorry to sound confused but isn't the problem your describing solved simply with Function Overloading ? i.e you implement both the MarchCubes(Field* pField) and a MarchCubes(BlobbyField* pBlobbyField) functions ?

Good question, what *am* I asking? Hmm...

Quote:
Original post by andygeers
do I have to accept the fact that I'm going to have to write a MarchBlobbyCubes(BlobbyField* pField) which is going to look totally different to the standard MarchCubes function?

I guess your answer is exactly that by another name (i.e. there's no difference in *design* between MarchBlobbyCubes(BlobbyField* pBlobbyField) and MarchCubes(BlobbyField* pBlobbyField)).

I think my question is how to stop messy spaghetti code in this situation - whilst MarchCubes(BlobbyField*) is different from MarchCubes(GenericField*), they still share a lot of common functionality.

Maybe the answer is just that anything that's in common between the two versions of the algorithm goes in a protected method that is shared, and the rest is always going to have to be written separately. But doesn't having lots of function calls inside your inner loops really slow things down? Maybe it's just because I always test in debug mode that function inlining doesn't take place.

ToohrVyk

238

ToohrVyk

Feb 24, 2007 at 6:36 AM

There is more to modular programming than just Object Oriented Programming. Generic Programming is also a great way to share code across multiple algorithms.

For instance, not so long ago, I had to write a filtering function: the principle is to compute a new pixel value based on the values of adjacent pixels, for every pixel in an image. Obviously, there is a lot of shared code between all possible filters (the iteration, the computing of the pixel positions), and the only variation is the function used to compute the new pixel value from the old ones. The Object-Oriented approach here is to represent this computation with an object. Obviously, it worked, but performance was lousy. In particular, there was no need for runtime polymorphism. The Generic approach provides an alternative to that by making the function a compile-time parameter of the filter (as opposed to a runtime one), which allowed inlining the function and thus increasing performance without losing the code sharing.

AndyGeers

Author

AndyGeers

Feb 24, 2007 at 11:47 AM

Quote:
Original post by ToohrVyk
There is more to modular programming than just Object Oriented Programming. Generic Programming is also a great way to share code across multiple algorithms.

Marching Cubes is sort of the opposite of that - you want to do the same bit of processing on each cube, but the difference is in which cubes you bother to visit. I guess in that case, some kind of iterator design pattern might be useful

BrianL

Feb 24, 2007 at 12:14 PM

Always remember that the API and the implementation of the functions in the API is separate. For example, you could have something like:

In the header:void MarchCubes(BlobbyField*);void MarchCubes(GenericField*);void MarchCubes(UniqueField*);...and in the implementation...template <typename T>static void SetupMarch(T* pField){    // Do common stuff}void MarchCubes(BlobbyField* pField){    SetupMarch(pField);    // Do the differentiating BlobbyField stuff}void MarchCubes(GenericField* pField){    SetupMarch(pField);    // Do the differentiating GenericField stuff}void MarchCubes(UniqueField* pField){    // Unique fields don't use any common code and require     // special code for everything.}

Basically, your implementations can either share code using abstraction, share code using generics, be differently, etc. The interface outwards and the internal implementation don't need to follow the same structural patterns.

Christer Ericson

Feb 24, 2007 at 1:13 PM

Quote:
Original post by ToohrVyk
There is more to modular programming than just Object Oriented Programming.

Yes! What is so frequently overlooked is that OOP is a means not an end! You don't use OOP because it is inherently better than everything else. It isn't! You use it where and when it furthers your goals. If it comes between you and your goal (and deep down you know when this happens, when you're bending over backwards to fit your code to some preconceived OOP idea, sacrificing other goals in the process) it is not only perfectly OK to not religiously use OOP in that situation, it is pragmatically the right thing to do!

Washu

Mod

375

Washu

Feb 24, 2007 at 1:51 PM

Quote:
Original post by AndyGeers
Quote:
Original post by ToohrVyk
There is more to modular programming than just Object Oriented Programming. Generic Programming is also a great way to share code across multiple algorithms.

Marching Cubes is sort of the opposite of that - you want to do the same bit of processing on each cube, but the difference is in which cubes you bother to visit. I guess in that case, some kind of iterator design pattern might be useful

Or, as nasty and overused as it is, a visitor pattern.

Having to make special cases of your marching cubes function typically indicates a break in LSP. It begs the question, is a BlobbyField really a Field, or are you just adding inheritance for the sake of inheritance?

Vorpy

Feb 24, 2007 at 4:05 PM

So you clearly have separate functions to perform marching cubes on BlobbyFields and on more general Fields. The BlobblyField simply provides more information that is useful for implementing the algorithm more efficiently.

The only way they can share the same implementation is if that implementation performs a check to see which type of field it is dealing with and then branches to the most efficient algorithm, which would be best implemented by writing each algorithm separately anyway.

The two implementations might still share some common code in the form of functions that they use when applicable.

You don't need to use inheritance to share code.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.