What design to use?

[rakeshthp]

Hello,

I am developing an application which can be used for digitize a geographical map through GUI and mouse interaction. Well, here are the list of objects that need to be created using mouse clicks.

1) Points
2) Polyline
3) Polygon
4) Rectangle/Square
5) Ellipse/Circle
6) Text

Can any one guide me what will be the best design which can be used to store the data(objects) more efficiently? So that both accessing objects and rendering them will be easier and faster? I have started with Composite Design pattern to store the objects and Visitor Design pattern to render these objects.

http://en.wikipedia.org/wiki/Composite_pattern
http://en.wikipedia.org/wiki/Visitor_pattern

But everytime rendering is done sequentially. Will not this take more time if the number of objects increases? Can anyone suggest me any other technique better and more efficient technique?

Thanks in advance

Regards

[nuzzle]

You don't have to use the same data structure for everything. In fact it's seldom optimal. Keeping the objects in an orderly fashion and displaying them quickly puts different demands on the data structure. The usual strategy is to generate a "display list" from the object data base.

It's the Builder pattern really. The "complex object" that's being built is the display list but you can also use it to build other data structures for other purposes of course, say printing on paper.

In practice the Component interface in Composite is enhanced with a build method (at least this is how I do it). This method traverses the Composite tree hierarchy and while it does that it also updates a Builder object that's passed in with the build method. The Builder object then builds a data structure such as a display list.

The creation of the display list may not be fast but the use of it should be. It should be very suitable for the fast feeding of the graphics driver (such as Direct3D). But still, you can never hope it will be better than linear in the number of objects. Not even if you traverse the display list in parallel. It will still be linear, only divided by a constant factor proportional to the number of available cores.

Also note that there's an upper limit to how much information the graphics driver can digest. If you feed it faster you'll have a bottleneck. This can be reduced by passing less information per object and/or writing cleverer shaders but still, there's an upper limit to how fast a display list must be. Beyond that you only get congestion.

So the Composite pattern is fine but you need to complement it with Builder which allows you to generate alternative data structures for special purposes such as a display list. Note that Builder is very similar to Visitor here. The difference is that Builder builds a display list whereas Visitor tries to be one.

Of course the display list strategy is useful only if rendering is more frequent than updates to the Composite data base. It's good if the Composite data base and the display list renderer run in different threads (and even better if both are separate from the GUI thread). This gives smooth operation of the application in spite of heavy CPU and GPU usage.

[D_Drmmr]

Can any one guide me what will be the best design which can be used to store the data(objects) more efficiently? So that both accessing objects and rendering them will be easier and faster? I have started with Composite Design pattern to store the objects and Visitor Design pattern to render these objects.

How did you apply the composite pattern? I don't see any variable-depth hierarchy in what you've described. The only "hierarchy" I see is the division in the six types of shapes that you've listed. That doesn't call for a composite pattern.

[rakeshthp]

How did you apply the composite pattern? I don't see any variable-depth hierarchy in what you've described. The only "hierarchy" I see is the division in the six types of shapes that you've listed. That doesn't call for a composite pattern.

Actually, there are two types of polyline. One is with points and another is without points (as shown in the attached image). So in case of polyline with points, There are three objects, one is polyline, second is node and third is vertex. So a special polyline is combination of Nodes, vertices and polyline. Am I right?

Is it the proper classification what I have done? If not, then please tell me which is the correct pattern to be used in this case.

Thanks in advance

[rakeshthp]

Dear nuzzle,

Thanks for that information. Actually, I am using visitor to perform draw operation. I have already used display lists in my application, but without builders. So according to you, I have to use Composite and Builder (in stead of visitors) is it?

Thanks

Regards

[nuzzle]

Thanks for that information. Actually, I am using visitor to perform draw operation. I have already used display lists in my application, but without builders. So according to you, I have to use Composite and Builder (in stead of visitors) is it?

Well, design patterns is not an exact science. And it's not about timorously applying them to the letter.

You have a design option here. Either you traverse the object data base and render at the same time, or you traverse it and generate a display list which is then rendered afterwards. I'd say the former is more in accordance with the Visitor pattern and the latter with Builder.

But even if you primarily use Builder nothing prevents you from using elements of Visitor. In the calls to the Builder interface the actual types of the Composite objects (such as maybe Point, Polygon and Text etcetera) can be revealed. That would be typical Visitor.

The major question is whether you gain something from extracting a display list. You do if you render it more often than it's updated. And a display list allows you to cleanly separate the rendering from the object management and run those in separate threads which may be beneficial.

[D_Drmmr]

Actually, there are two types of polyline. One is with points and another is without points (as shown in the attached image). So in case of polyline with points, There are three objects, one is polyline, second is node and third is vertex. So a special polyline is combination of Nodes, vertices and polyline. Am I right?

I'm not sure what you are trying to say exactly. Do you want to distinguish a polyline that displays its points from one that doesn't? Or are there other differences between the two types? Or are you just saying you want to model a polyline as a collection of points and lines?

In any case, the fact that your polyline can be represented (and drawn) as a set of points and lines does not imply that you should use the composite pattern. You could derive a class PolyLine (or PolyLineWithPoints) from a CompositeShape, but you probably wouldn't gain much from doing so, instead of just storing a bunch of points (in order) in a PolyLine object.

If you want to achieve good performance, then you should be reluctant to use runtime polymorphism in elements of your code that will occur inside performance-critical loops. An approach using parallel homogeneous arrays of each type of shape or using a variant type (see e.g. boost::variant) is likely to give better results in terms of performance.

[rakeshthp]

I'm not sure what you are trying to say exactly. Do you want to distinguish a polyline that displays its points from one that doesn't? Or are there other differences between the two types? Or are you just saying you want to model a polyline as a collection of points and lines?

Yes, I mean to say that I want to model a polyline as a collection of points and lines. i.e. This is what is required to implement. There are three things that can be picked(selected) when it comes to object of type PolyLinesWithPoints. One is continuous polyline(single line must be picked), second is vertex and third is node. When a node/vertex is picked, it will have it's own ID and other properties. And when this node/vertex is moved using point, the polyline also must be updated accordingly.

Whereas, in simple polyline, there are no nodes/vertices. It is displayed as a simple polyline. Only when it picked, it will show it's control points, which are later used to edit/move it.

Notable difference is that, Polyline (entire line) can be directly moved using mouse, whereas, PolylineWithPoints cannot be moved. Only it's vertices/nodes needs to be adjusted to move. I hope this is clear

In any case, the fact that your polyline can be represented (and drawn) as a set of points and lines does not imply that you should use the composite pattern. You could derive a class PolyLine (or PolyLineWithPoints) from a CompositeShape, but you probably wouldn't gain much from doing so, instead of just storing a bunch of points (in order) in a PolyLine object.

If you want to achieve good performance, then you should be reluctant to use runtime polymorphism in elements of your code that will occur inside performance-critical loops. An approach using parallel homogeneous arrays of each type of shape or using a variant type (see e.g. boost::variant) is likely to give better results in terms of performance.

Initially I had used the same runtime polymorphism and

std::map<object_id, object>

to store the objects. But I felt, during iterating the map, performance would reduce (for large number of objects). Isn't it? So should I go ahead with runtime polymorphism approach?

One more thing is that I came across this article here

http://www.datasim.nl/Education/Arti...itePaper2.html

Based on this article I changed my design.