Welcome! Log In Create A New Profile

Advanced
Re: T-Junctions re-visited
March 20, 2013 06:42AM
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
T-Junctions re-visited Travis Cobbs710March 11, 2013 10:38PM
Re: T-Junctions re-visited Tim Gould347March 11, 2013 11:31PM
Re: T-Junctions re-visited Roland Melkert329March 12, 2013 11:17AM
Re: T-Junctions re-visited Ben Supnik330March 12, 2013 11:17AM
Re: T-Junctions re-visited Roland Melkert318March 12, 2013 11:22AM
Re: T-Junctions re-visited Ben Supnik300March 12, 2013 11:32AM
Re: T-Junctions re-visited Roland Melkert299March 12, 2013 11:41AM
Re: T-Junctions re-visited Ben Supnik313March 12, 2013 11:55AM
Re: T-Junctions re-visited Roland Melkert311March 13, 2013 10:08AM
Re: T-Junctions re-visited Travis Cobbs334March 13, 2013 11:27AM
Re: T-Junctions re-visited Allen Smith339March 12, 2013 02:01PM
Re: T-Junctions re-visited Michael Heidemann322March 13, 2013 09:27AM
Re: T-Junctions re-visited Ben Supnik307March 13, 2013 10:37AM
Re: T-Junctions re-visited Tim Gould304March 13, 2013 02:31PM
Re: T-Junctions re-visited Michael Heidemann298March 13, 2013 03:42PM
Re: T-Junctions re-visited Michael Heidemann321March 17, 2013 04:35AM
Re: T-Junctions re-visited Ben Supnik271March 17, 2013 08:43AM
Re: T-Junctions re-visited Michael Heidemann273March 17, 2013 08:59AM
Re: T-Junctions re-visited Ben Supnik277March 17, 2013 09:02AM
Re: T-Junctions re-visited Magnus Forsberg287March 17, 2013 09:15AM
Re: T-Junctions re-visited Travis Cobbs348March 17, 2013 10:09PM
Re: T-Junctions re-visited Ben Supnik308March 18, 2013 07:30AM
Re: T-Junctions re-visited Travis Cobbs308March 18, 2013 10:57AM
Re: T-Junctions re-visited Ben Supnik317March 18, 2013 11:27AM
Re: T-Junctions re-visited Travis Cobbs303March 18, 2013 12:23PM
Re: T-Junctions re-visited Ben Supnik325March 18, 2013 01:41PM
Re: T-Junctions re-visited Roland Melkert338March 18, 2013 02:51PM
Re: T-Junctions re-visited Travis Cobbs309March 18, 2013 02:59PM
Re: T-Junctions re-visited Roland Melkert376March 18, 2013 03:41PM
Re: T-Junctions re-visited Ben Supnik345March 18, 2013 06:09PM
Re: T-Junctions re-visited Roland Melkert320March 19, 2013 11:38AM
Re: T-Junctions re-visited Ben Supnik338March 19, 2013 11:43AM
Re: T-Junctions re-visited Roland Melkert354March 19, 2013 07:07PM
Re: T-Junctions re-visited Travis Cobbs326March 19, 2013 10:13PM
Re: T-Junctions re-visited Tim Gould320March 20, 2013 03:56AM
Re: T-Junctions re-visited Travis Cobbs307March 20, 2013 10:13AM
Re: T-Junctions re-visited Ben Supnik295March 20, 2013 10:23AM
Re: T-Junctions re-visited Travis Cobbs317March 20, 2013 10:29AM
Re: T-Junctions re-visited Travis Cobbs309March 20, 2013 10:26AM
Re: T-Junctions re-visited Ben Supnik289March 20, 2013 11:18AM
Re: T-Junctions re-visited Ben Supnik311March 20, 2013 06:42AM
Re: T-Junctions re-visited Roland Melkert288March 20, 2013 11:36AM
Re: T-Junctions re-visited Philippe Hurbain307March 20, 2013 06:36AM
Re: T-Junctions re-visited Ben Supnik350March 20, 2013 06:58AM
Re: T-Junctions re-visited Allen Smith333March 20, 2013 09:08AM
Re: T-Junctions re-visited Roland Melkert335March 20, 2013 11:35AM
Re: T-Junctions re-visited Ben Supnik744March 20, 2013 11:50AM
Re: T-Junctions re-visited Michael Heidemann342March 18, 2013 03:54PM
Re: T-Junctions re-visited Roland Melkert303March 13, 2013 10:03AM
Re: T-Junctions re-visited Tim Gould275March 13, 2013 03:56PM
Re: T-Junctions re-visited Sergio Reano281March 13, 2013 03:51PM
Re: T-Junctions re-visited Roland Melkert350March 13, 2013 04:36PM
Re: T-Junctions re-visited Tim Gould308March 13, 2013 05:10PM
Re: T-Junctions re-visited Ben Supnik310March 14, 2013 08:17PM
Re: T-Junctions re-visited Tim Gould354March 14, 2013 08:41PM
Re: T-Junctions re-visited Ben Supnik354March 15, 2013 10:56AM
Re: T-Junctions re-visited Roland Melkert299March 15, 2013 11:36AM
Re: T-Junctions re-visited Ben Supnik269March 13, 2013 06:58PM
Re: T-Junctions re-visited Roland Melkert282March 13, 2013 07:27PM
Re: T-Junctions re-visited Ben Supnik264March 13, 2013 07:37PM
Re: T-Junctions re-visited Roland Melkert288March 13, 2013 07:59PM
Re: T-Junctions re-visited Ben Supnik309March 13, 2013 08:18PM
Re: T-Junctions re-visited Travis Cobbs342March 14, 2013 03:23PM
Re: T-Junctions re-visited Roland Melkert355March 14, 2013 03:34PM
Re: T-Junctions re-visited Tim Gould358March 14, 2013 03:41PM
Re: T-Junctions re-visited Roland Melkert338March 15, 2013 11:33AM
Re: T-Junctions re-visited Tim Gould294March 13, 2013 07:43PM
Re: T-Junctions re-visited Roland Melkert286March 13, 2013 08:08PM
Re: T-Junctions re-visited Tim Gould292March 13, 2013 08:18PM
Re: T-Junctions re-visited Ben Supnik361March 14, 2013 08:15PM
Re: T-Junctions re-visited Roland Melkert351March 15, 2013 11:29AM
Re: T-Junctions re-visited Travis Cobbs334March 15, 2013 12:27PM
Re: T-Junctions re-visited Ben Supnik333March 15, 2013 05:08PM
Re: T-Junctions re-visited Travis Cobbs338March 16, 2013 11:29PM
Re: T-Junctions re-visited Ben Supnik266March 17, 2013 08:58AM
Re: T-Junctions re-visited Roland Melkert266March 17, 2013 12:35PM
Re: T-Junctions re-visited Travis Cobbs305March 18, 2013 12:28PM
Re: T-Junctions re-visited Travis Cobbs356March 18, 2013 12:32PM
Re: T-Junctions re-visited Roland Melkert318March 18, 2013 05:00PM
Re: T-Junctions re-visited Travis Cobbs349March 18, 2013 11:05PM
Re: T-Junctions re-visited Roland Melkert384March 19, 2013 11:38AM
Re: T-Junctions re-visited Sergio Reano352March 26, 2013 02:46PM
Re: T-Junctions re-visited Roland Melkert295March 27, 2013 11:19AM
Re: T-Junctions re-visited Sergio Reano365March 27, 2013 01:48PM



Sorry, only registered users may post in this forum.

Click here to login