Από τον Delaunay στον αλγόριθμο ear clipping
Ο τριγωνισμός χαρτογραφικών δεδομένων αποτελεί κρίσιμο σημείο συμφόρησης (bottleneck) για τους renderers. Ενώ ο Constrained Delaunay Triangulator προσφέρει υψηλή ποιότητα τριγώνων, το υπολογιστικό του κόστος είναι απαγορευτικό για εκατομμύρια πολύγωνα. Η μετάβαση στο ear clipping, με κατάλληλες βελτιστοποιήσεις, επιτρέπει την ταχύτερη επεξεργασία, καθώς τα περισσότερα πολύγωνα χαρτών δεν απαιτούν την αυστηρή γεωμετρική ακρίβεια του Delaunay.
Αρχιτεκτονικές βελτιστοποιήσεις για ταχύτητα
Η ομάδα του earstrip εισήγαγε μια σειρά από τεχνικές για να επιταχύνει τον έλεγχο των «αυτιών» (ears) ενός πολυγώνου:
- Διαχείριση Dents: Αντί για εξαντλητικό έλεγχο όλων των κορυφών, ο αλγόριθμος διατηρεί μια λίστα με reflex vertices (dents), περιορίζοντας δραστικά τον χώρο αναζήτησης.
- Branchless Counting: Η χρήση bitwise πράξεων για την καταμέτρηση σημείων εντός τριγώνων εξαλείφει τις διακλαδώσεις (branches), επιτρέποντας στον CPU να εκτελεί τον κώδικα με πολύ μεγαλύτερη ροή.
- Triangle Strips: Αντί για την αποθήκευση τριών δεικτών ανά τρίγωνο, η παραγωγή triangle strips μειώνει τον όγκο των δεδομένων που αποστέλλονται στη GPU, βελτιώνοντας το throughput.
Διαλειτουργικότητα και WebAssembly
Η βιβλιοθήκη σχεδιάστηκε με γνώμονα τη διαλειτουργικότητα (interoperability) μεταξύ native C++ και WebAssembly. Οι μετρήσεις δείχνουν ότι το earstrip διατηρεί το προβάδισμά του και στον browser, ξεπερνώντας το earcut.js έως και 2.1 φορές. Η στρατηγική της μεταφοράς ολόκληρων συνόλων δεδομένων στο memory space του WASM module, αντί για μεμονωμένες κλήσεις ανά πολύγωνο, αποδείχθηκε καθοριστική για την εξάλειψη του overhead της γέφυρας JS-WASM.