What design to use?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: What design to use?

  1. #1
    Join Date
    Jul 2009
    Location
    Bangalore, INDIA
    Posts
    45

    What design to use?

    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

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: What design to use?

    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.
    Last edited by nuzzle; July 9th, 2012 at 06:34 AM.

  3. #3
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,016

    Re: What design to use?

    Quote Originally Posted by rakeshthp View Post
    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.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  4. #4
    Join Date
    Jul 2009
    Location
    Bangalore, INDIA
    Posts
    45

    Re: What design to use?

    Quote Originally Posted by D_Drmmr View Post
    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


    Name:  polyline_types.PNG
Views: 56
Size:  5.7 KB

  5. #5
    Join Date
    Jul 2009
    Location
    Bangalore, INDIA
    Posts
    45

    Re: What design to use?

    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

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: What design to use?

    Quote Originally Posted by rakeshthp View Post
    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.
    Last edited by nuzzle; July 10th, 2012 at 01:03 AM.

  7. #7
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,016

    Re: What design to use?

    Quote Originally Posted by rakeshthp View Post
    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.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  8. #8
    Join Date
    Jul 2009
    Location
    Bangalore, INDIA
    Posts
    45

    Re: What design to use?

    Quote Originally Posted by D_Drmmr View Post
    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

    Quote Originally Posted by D_Drmmr View Post
    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
    Code:
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center