An Efficient point-in-convex 3D polyhedron test using a projective algorithm with sub-linear expected complexity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F25%3A43976476" target="_blank" >RIV/49777513:23520/25:43976476 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/content/pdf/10.1007/s00138-025-01743-3.pdf" target="_blank" >https://link.springer.com/content/pdf/10.1007/s00138-025-01743-3.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00138-025-01743-3" target="_blank" >10.1007/s00138-025-01743-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

An Efficient point-in-convex 3D polyhedron test using a projective algorithm with sub-linear expected complexity

Popis výsledku v původním jazyce

We propose a novel algorithm for determining whether a given point lies within a convex polyhedron, achieving a sub-linear computational expected complexity of Oexp(N1/2), where N represents the number of triangles in the polyhedron’s triangular mesh. In contrast to traditional methods with linear complexity O(N), our approach significantly reduces com-putational overhead, making it especially effective for large polyhedral models. The algorithm is formulated entirely in projective space, utilizing homogeneous coordinates for the tested points and triangle vertices. By leveraging vector–vec¬tor operations optimized for SSE, AVX instructions, and GPU architectures, our method is robust and straightforward, tailored to handle even highly complex convex polyhedra. The efficiency of the approach was validated through theoretical analysis and estimated speed-up calculations, demonstrating its potential to accelerate applications in computer graphics, computational geometry, collision detection, and related fields. Additionally, the simplicity of the proposed algorithm ensures a high potential for broad applicability and supports further advancements in this area.

Název v anglickém jazyce

An Efficient point-in-convex 3D polyhedron test using a projective algorithm with sub-linear expected complexity

Popis výsledku anglicky

We propose a novel algorithm for determining whether a given point lies within a convex polyhedron, achieving a sub-linear computational expected complexity of Oexp(N1/2), where N represents the number of triangles in the polyhedron’s triangular mesh. In contrast to traditional methods with linear complexity O(N), our approach significantly reduces com-putational overhead, making it especially effective for large polyhedral models. The algorithm is formulated entirely in projective space, utilizing homogeneous coordinates for the tested points and triangle vertices. By leveraging vector–vec¬tor operations optimized for SSE, AVX instructions, and GPU architectures, our method is robust and straightforward, tailored to handle even highly complex convex polyhedra. The efficiency of the approach was validated through theoretical analysis and estimated speed-up calculations, demonstrating its potential to accelerate applications in computer graphics, computational geometry, collision detection, and related fields. Additionally, the simplicity of the proposed algorithm ensures a high potential for broad applicability and supports further advancements in this area.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Machine Vision and Applications

ISSN

0932-8092

e-ISSN

1432-1769

Svazek periodika

36

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

1-11

Kód UT WoS článku

001591025700001

EID výsledku v databázi Scopus

—