Re: T-Junctions re-visited
 March 20, 2013 06:42AM LDraw Part Author Registered: 2 years agoPosts: 185
Hi Travis,

I'm using a related technique: I have a single array of vertices, but they are sorted by a "lexicographal" comparison function (that is, sort by X, if X is equal sort by Y, if Y is equal, sort by Z, etc.).

This gives you similar performance times as the balanced binary tree - NlogN to get the index built (due to sort time) and log-time lookups via a binary search.

The big thing you lose with the array is cheap insertion of "more stuff." But in the case of my code, I know the total vertex count before I even start working (because I have the unsmoothed directive and can count up the triangles and quads and lines) so this is acceptable.

The other thing I discovered is that, given a vertex in the array, it is a bit faster to find the range of equal vertices by linear search (E.g. just walk in both directions in the array) than to do a binary search of the whole sorted array. I chalk this up to locality - more cache hits if the search stays close by. I've been meaning to do a 'step' search - that is, start in the array, walk in units of N vertices, then walk back by N/2, etc. If we start N at a small number like 16 or so, we can find groups of equal value vertices in only a few steps. But...performance profiles indicate that it's a small optimization at this point; the algorithm is currently dominated by the 'big sort' at the beginning.

I'm currently sorting the _entire_ part together -- lines and tris and quads. When I had the lines separate it was faster (it's quicker to sort two small things than one big thing) but I want to have one 'pile' of vertices for snapping things together, so I think one big pile it is.

I think the big win is going to be recursion optimizations, e.g. smooth the stud, recognize in the smoothing process that the stud is "sealed" from other parts and doesn't need to be resmoothed when it is included, then smooth the parent part without the studs. I base this on the fact that (1) my code can detect that the stud is sealed and (2) small parts optimize almost instantly and (3) the big baseplates minus studs have similar vertex counts to small parts. It's a big refactor to actually get the code working this way though; I'm going to finish T junction repair first.

Cheers
Ben
SubjectAuthorViewsPosted
Travis Cobbs741March 11, 2013 10:38PM
Tim Gould365March 11, 2013 11:31PM
Roland Melkert342March 12, 2013 11:17AM
Ben Supnik360March 12, 2013 11:17AM
Roland Melkert338March 12, 2013 11:22AM
Ben Supnik331March 12, 2013 11:32AM
Roland Melkert318March 12, 2013 11:41AM
Ben Supnik331March 12, 2013 11:55AM
Roland Melkert326March 13, 2013 10:08AM
Travis Cobbs353March 13, 2013 11:27AM
Allen Smith352March 12, 2013 02:01PM
Michael Heidemann340March 13, 2013 09:27AM
Ben Supnik323March 13, 2013 10:37AM
Tim Gould329March 13, 2013 02:31PM
Michael Heidemann315March 13, 2013 03:42PM
Michael Heidemann348March 17, 2013 04:35AM
Ben Supnik287March 17, 2013 08:43AM
Michael Heidemann282March 17, 2013 08:59AM
Ben Supnik281March 17, 2013 09:02AM
Magnus Forsberg308March 17, 2013 09:15AM
Travis Cobbs355March 17, 2013 10:09PM
Ben Supnik322March 18, 2013 07:30AM
Travis Cobbs317March 18, 2013 10:57AM
Ben Supnik325March 18, 2013 11:27AM
Travis Cobbs316March 18, 2013 12:23PM
Ben Supnik340March 18, 2013 01:41PM
Roland Melkert359March 18, 2013 02:51PM
Travis Cobbs335March 18, 2013 02:59PM
Roland Melkert407March 18, 2013 03:41PM
Ben Supnik375March 18, 2013 06:09PM
Roland Melkert328March 19, 2013 11:38AM
Ben Supnik345March 19, 2013 11:43AM
Roland Melkert372March 19, 2013 07:07PM
Travis Cobbs343March 19, 2013 10:13PM
Tim Gould335March 20, 2013 03:56AM
Travis Cobbs316March 20, 2013 10:13AM
Ben Supnik305March 20, 2013 10:23AM
Travis Cobbs339March 20, 2013 10:29AM
Travis Cobbs320March 20, 2013 10:26AM
Ben Supnik298March 20, 2013 11:18AM
Ben Supnik330March 20, 2013 06:42AM
Roland Melkert301March 20, 2013 11:36AM
Philippe Hurbain331March 20, 2013 06:36AM
Ben Supnik384March 20, 2013 06:58AM
Allen Smith357March 20, 2013 09:08AM
Roland Melkert384March 20, 2013 11:35AM
Ben Supnik778March 20, 2013 11:50AM
Michael Heidemann363March 18, 2013 03:54PM
Roland Melkert328March 13, 2013 10:03AM
Tim Gould295March 13, 2013 03:56PM
Sergio Reano285March 13, 2013 03:51PM
Roland Melkert364March 13, 2013 04:36PM
Tim Gould313March 13, 2013 05:10PM
Ben Supnik340March 14, 2013 08:17PM
Tim Gould379March 14, 2013 08:41PM
Ben Supnik376March 15, 2013 10:56AM
Roland Melkert320March 15, 2013 11:36AM
Ben Supnik284March 13, 2013 06:58PM
Roland Melkert291March 13, 2013 07:27PM
Ben Supnik286March 13, 2013 07:37PM
Roland Melkert307March 13, 2013 07:59PM
Ben Supnik318March 13, 2013 08:18PM
Travis Cobbs381March 14, 2013 03:23PM
Roland Melkert382March 14, 2013 03:34PM
Tim Gould366March 14, 2013 03:41PM
Roland Melkert371March 15, 2013 11:33AM
Tim Gould331March 13, 2013 07:43PM
Roland Melkert291March 13, 2013 08:08PM
Tim Gould309March 13, 2013 08:18PM
Ben Supnik378March 14, 2013 08:15PM
Roland Melkert374March 15, 2013 11:29AM
Travis Cobbs351March 15, 2013 12:27PM
Ben Supnik343March 15, 2013 05:08PM
Travis Cobbs356March 16, 2013 11:29PM
Ben Supnik273March 17, 2013 08:58AM
Roland Melkert278March 17, 2013 12:35PM
Travis Cobbs316March 18, 2013 12:28PM
Travis Cobbs384March 18, 2013 12:32PM
Roland Melkert339March 18, 2013 05:00PM
Travis Cobbs364March 18, 2013 11:05PM
Roland Melkert409March 19, 2013 11:38AM
Sergio Reano359March 26, 2013 02:46PM
Roland Melkert304March 27, 2013 11:19AM
Sergio Reano386March 27, 2013 01:48PM

Sorry, only registered users may post in this forum.