BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Polygon rasterizer          BorlandTalk.com Forum Index -> Delphi Graphics View previous topic :: View next topic   Author Message Tomaz Koritnik Guest Posted: Thu Jun 03, 2004 8:41 pm    Post subject: Polygon rasterizer Hi I'm trying to make my polygon rasterizer to work faster. I'm calculating intersections with line Y = const and sort them. Sorting takes 90% of all rasterizing time, so optimizing the sorting itself is the key. So far I use linked list with optimized search but GDI is still 3x faster. Does anyone has any better idea of how to do this faster? I don't want examples, but an idea of how to make this. regards Tomaz Back to top Alexey Barkovoy Guest Posted: Fri Jun 04, 2004 7:43 am    Post subject: Re: Polygon rasterizer Not enought data from you. Quote: I'm trying to make my polygon rasterizer to work faster. I'm calculating intersections with line Y = const and sort them. Sorting takes 90% of all rasterizing time, so optimizing the sorting itself is the key. So far I use linked list with optimized search but GDI is still 3x faster. Does anyone has any better idea of how to do this faster? I don't want examples, but an idea of how to make this. Back to top Tomaz Koritnik Guest Posted: Fri Jun 04, 2004 4:39 pm    Post subject: Re: Polygon rasterizer Hi What kind of data would you like? The main slowdown is sorting selected intersections. I have a linked list of them but this is just one of data structures. When I calculate new intersection, I search from beginning of list until I found the insertion place. I made it faster to use another linked list where each item holds every 10th item from the first list, therefore skipping 9 items. I can do that because list is sorted. I made my rasterizer arround 2x faster with this but it's still 2.5x slower than GDI. Maybee there's another way to sort intersections. regards Tomaz "Alexey Barkovoy" <gate21 (AT) mail (DOT) ru> wrote Quote: Not enought data from you. I'm trying to make my polygon rasterizer to work faster. I'm calculating intersections with line Y = const and sort them. Sorting takes 90% of all rasterizing time, so optimizing the sorting itself is the key. So far I use linked list with optimized search but GDI is still 3x faster. Does anyone has any better idea of how to do this faster? I don't want examples, but an idea of how to make this. Back to top Anders Isaksson Guest Posted: Fri Jun 04, 2004 7:41 pm    Post subject: Re: Polygon rasterizer Tomaz Koritnik wrote: Quote: I'm trying to make my polygon rasterizer to work faster. I'm calculating intersections with line Y = const and sort them. Sorting takes 90% of all rasterizing time, so optimizing the sorting itself is the key. What sorting routine are you using? How many intersections do you have to sort? Can you give example code? I'm not at all sure the the sorting by itself is the bottleneck. Are you sure you need to sort everything you put up for sorting? Are you rearranging the linked list when doing swaps? How much memory is moved in each swap? 'My' polygon rasterizer in BlockCAD is 2-50 times faster than GDI, but I didn't invent it myself - I converted a routine in C (by Paul Heckbert) I found in Graphical Gems. This routine uses a plain Bubble sort both for sorting the polygon points by Y (once), and the ActiveEdges list by X (once per scanline covered by the polygon). The amount of data to sort each time is mostly very small, unless you have very complex polygons, so the Bubble sort with zero overhead is quite effective. The actual points are never swapped, all access goes through one layer of indirection, to minimize the amount of memory to move in each swap. -- Anders Isaksson, Sweden BlockCAD: http://w1.161.telia.com/~u16122508/proglego.htm Gallery: http://w1.161.telia.com/~u16122508/gallery/index.htm Back to top Anders Isaksson Guest Posted: Fri Jun 04, 2004 7:46 pm    Post subject: Re: Polygon rasterizer Tomaz Koritnik wrote: Quote: When I calculate new intersection, I search from beginning of list until I found the insertion place. I made it faster to use another linked list where each item holds every 10th item from the first list, therefore skipping 9 items. I can do that because list is sorted. I made my rasterizer arround 2x faster with this but it's still 2.5x slower than GDI. Maybee there's another way to sort intersections. Do you generate *all* intersections, for the whole polygon, at once? Then your linked list will be quite long, and the linear search you do to find the insertion point will explain most of the slowness. Work one scanline at a time, and your list will mostly only contain two points, which are quite easily sorted :-) If you must have really long lists, then I recommend a tree instead. The insertion will be much faster (Like comparing linear search to binary search). -- Anders Isaksson, Sweden BlockCAD: http://w1.161.telia.com/~u16122508/proglego.htm Gallery: http://w1.161.telia.com/~u16122508/gallery/index.htm Back to top Tomaz Koritnik Guest Posted: Fri Jun 04, 2004 9:50 pm    Post subject: Re: Polygon rasterizer Hi Quote: Do you generate *all* intersections, for the whole polygon, at once? No, I do calculation for each scanline separately. Quote: the insertion point will explain most of the slowness. Work one scanline at a time, and your list will mostly only contain two points, which are quite easily sorted Yes, most of the time, there will be just a couple of points. But the main idea is to reproduce speed at which GDI is working as I would really like to know how GDI's rasterizer is implemented. regards Tomaz Back to top Lord Crc Guest Posted: Sat Jun 05, 2004 11:19 am    Post subject: Re: Polygon rasterizer On Thu, 3 Jun 2004 22:41:16 +0200, "Tomaz Koritnik" <nospam (AT) nospam (DOT) com> wrote: Quote: Does anyone has any better idea of how to do this faster? I don't want examples, but an idea of how to make this. By polygons do you mean polygons or triangles? Cause for triangles there's some pretty quick ways out there. Anyway, for sorting, which method are you using? Insertion? How about a preallocated buffer for each scanline, which you can grow on demand, and use quicksort? Cause for my median filter i had to sort 5x5 samples, and found quicksort to be faster than insertion or bubble. - Asbjørn Back to top Tomaz Koritnik Guest Posted: Sat Jun 05, 2004 6:15 pm    Post subject: Re: Polygon rasterizer Hi Quote: By polygons do you mean polygons or triangles? Cause for triangles there's some pretty quick ways out there. No, complex polygons. Quote: Anyway, for sorting, which method are you using? Insertion? How about a preallocated buffer for each scanline, which you can grow on demand, and use quicksort? Cause for my median filter i had to sort 5x5 samples, and found quicksort to be faster than insertion or bubble. I use a list for each scanline. I choosed linked list instead of array because inserting items is easy, but searching is slower. I'm inserting items into list when I calculate them, not at the end. This is slow because for each intersection calculated, I need to go from beginning to the insection place. Optimization was to skip some items and check i.e. avery 10th item. This made things 2x faster but GDI still does it much faster . regards Tomaz Back to top Lord Crc Guest Posted: Sat Jun 05, 2004 9:29 pm    Post subject: Re: Polygon rasterizer On Sat, 5 Jun 2004 20:15:35 +0200, "Tomaz Koritnik" <nospam (AT) nospam (DOT) com> wrote: Quote: This made things 2x faster but GDI still does it much faster . Just to compare software to software, set Graphics Acceleration to none when testing this. Else GDI could very well be using hardware acceleration, in which case you dont have a chance :) - Asbjørn Back to top Tomaz Koritnik Guest Posted: Sun Jun 06, 2004 9:08 am    Post subject: Re: Polygon rasterizer Hi Quote: none when testing this. Else GDI could very well be using hardware acceleration, in which case you dont have a chance I don't think hardware acceleration is possible in case of memory bitmaps. But it's true, drawing a polygon to DDB is ultra fast because of accelerattion. regards Tomaz Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> Delphi Graphics All times are GMT Page 1 of 1   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.