Generating Sequential Triangle Strips by using Hopfield Nets

0405294 - UIVT-O 330626 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Šíma, Jiří
Generating Sequential Triangle Strips by using Hopfield Nets.
[Generování sekvenčních trojúhelníkových pásů pomocí Hopfieldových sítí.]
Adaptive and Natural Computing Algorithms. Wien: Springer-Verlag, 2005 - (Ribiero, B.; Albrecht, R.; Dobnikar, A.; Pearson, D.; Steele, N.), s. 25-28. ISBN 3-211-24934-6.
[ICANNGA'2005 /7./. Coimbra (PT), 21.03.2005-23.03.2005]
Grant CEP: GA MŠMT(CZ) 1M0545; GA MŠMT LN00A056
Klíčová slova: sequential triangle strip * combinatorial optimization * Hopfield network * minimum energy * simulated annealing
Kód oboru RIV: BA - Obecná matematika

The important task of generating the minimum number of sequential triangle strips (tristrips) for a given triangulated surface model is motived by applications in computer graphics. This hard combinatorial optimization problem is reduced to the minimum energy problem in Hopfield nets by a linear-size construction. The Hopfield network powered by simulated annealing (i.e. Boltzmann machine) which is implemented in a program HTGEN can be used for computing the semi-optimal stripifications. Practical experiments confirm that one can obtain much better results using HTGEN than by a leading stripification program FTSG although the running time of simulated annealing grows rapidly near the global optimum.

Důležitá úloha generování minimálního počtu sekvenčních trojúhelníkových pásů (tristrips) pro daný triangulovaný povrchový model je motivována aplikacemi v počítačové grafice. Tento těžký kombinatorický problém je redukován na problém minimální energie v Hopfieldových sítích pomocí konstrukce lineární velikosti. Hopfieldovu síť obohacenou o simulované žíhání (tj. Boltzmannův stroj), která je implementována v programu HTGEN, lze použít k výpočtu semioptimálních stripifikací. Praktické experimenty potvrzují, že použitím HTGEN lze získat mnohem lepší výsledky než pomocí vedoucího stripifikačního programu FTSG, i když výpočetní čas simulovaného žíhání roste rychle v blízkosti globálního optima.
Trvalý link: http://hdl.handle.net/11104/0125474