Subject:
|
Re: Some secrets of MLCad revealed ...
|
Newsgroups:
|
lugnet.cad.mlcad
|
Date:
|
Mon, 7 Jul 2003 00:30:14 GMT
|
Viewed:
|
7171 times
|
| |
|
|
In lugnet.cad.mlcad, Michael Lachmann wrote:
> "Damien Guichard" <damien.guichard@wanadoo.fr> schrieb im Newsbeitrag
> news:HHKMxB.225G@lugnet.com...
> <SNIP>
> > Thanks Michael.
> > So, at loading time, each added point has to be compared to all points in the
> > point list. Does this impact the loading time of big parts or big models in a
> > significant manner? Or is it only minor slowdown?
> >
> > Regards,
> >
> > Damien
>
> So far I could find out, it doesn't effect loading much, I think it was
> something about 10% less then without this feature. I must say, I haven't
> tried using hash algorythms to find the point more quickly, but so far I
> remember there is an average of arround 400 points in a file, and search for
> an 12 byte value is not so hard ...
>
> Michael
Ok, the practical figures relativize the problem for everyday use.
Thanks Michael.
For the sake of sharing here is how I imagine a sorted point list.
The sorted list is also implemented as an array, so points can be accessed by
index for rendering.
But the array is organized as a 3-keys binary tree.
So a point is not simply added at end, but compared to a pivot, much like in a
quicksort algorithm.
The pivot is the middle item of the array.
If the x-coord of the added item is smaller than the pivot's x-coord then the
item is added in the sub-array at left of the pivot.
If the x-coord of the added item is greater than the pivot's x-coord then the
item is added in the sub-array at right of the pivot.
The new pivot is the middle item of this sub-array.
If the y-coord ... smaller than the pivot's y-coord ... left ...
If the y-coord ... greater than the pivot's y-coord ... right ...
The new pivot is the middle item of the new sub-array.
If the z-coord ... smaller than the pivot's z-coord ... left ...
If the z-coord ... greater than the pivot's z-coord ... right ...
Then again compare x-coord, then y-coord, then z-coord until the sub-array is
reduced to a single item.
Then the new item is inserted at left or at right of the pivot depending the
comparison, much like a binary tree.
And point search is also much like a binary tree.
Pretty useless and does not worth the effort, yet an elegant data structure.
Regards,
Damien
|
|
Message has 1 Reply:
 | | Re: Some secrets of MLCad revealed ...
|
| (...) <snip> Cool! Should perform a lot faster on searching I would expect 400 points? That seems low to me. Most of my models have more than that many elements! Even with shared vertices that seems low. (23 years ago, 7-Jul-03, to lugnet.cad.mlcad)
|
Message is in Reply To:
| | Re: Some secrets of MLCad revealed ...
|
| "Damien Guichard" <damien.guichard@wanadoo.fr> schrieb im Newsbeitrag news:HHKMxB.225G@lugnet.com... <SNIP> (...) the (...) in a (...) So far I could find out, it doesn't effect loading much, I think it was something about 10% less then without this (...) (23 years ago, 6-Jul-03, to lugnet.cad.mlcad)
|
12 Messages in This Thread:
  
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
