Publicado el 14 de Enero del 2017
563 visualizaciones desde el 14 de Enero del 2017
182,7 MB
143 paginas
Creado hace 11a (14/02/2013)
CUTRe OE IWYESTIGACIU VII
£ST UOlOS HH1l~ I)OS U l
I. P. N.
B I BL IOT EC-'1
"lt>EN I£R!A ELECTRICA
CENTRO DE INVESTIGACION Y DE
ESTUDIOS A V ANZADOS DEL lPN
Departamento de Ingenieria Eh~ctrica
Secci6n de Computaci6n
IMPLANTACION DE OPERACIONES BOOLEANAS
SOBRE SOLIDOS REPRESENT ADOS CON UNA
ESTRUCTURA BASADA EN ARISTAS
I S / CIN 'rSrAv
I ADQ'JISIC . 'J
DE UBROS
lPN
I
T E s
Que para obtener el grado de
Maestro en Ciencias
En Ia especialidad de lngenierfa Electrica
P R E S E N T A
Marco Antonio Perez Flores
Mexico, D. F.
marzo de 1992
Este trabajo se realiz6 en las instalaciones de Ia Secci6n de
Computaci6n del Depanamento de lngenieria Electrica del
Centro de lnvestigaci6n y de Estudios Avanzados del lPN,
bajo Ia direce16n del M. C. Feliu D. Sagols Troncoso.
CfHTM DE INVlSTIGACION y I!
rsrur.ros J. VJ, ,•1ztoos l!fl
I. P. N .
I B LI OT E C A
•
INGENIERIA ElECTR/CA
este
deseo
conducto,
Par
expresar mi
agradecimiento al Consejo Nacional de Ciencia y
Tecnologia, por el apoyo econ6mico que me brind6
para Ia realizaci6n de mis estudios de Maestrfa y Ia
elaboraci6n del presente trabajo de Tesis.
CliT~I Dt I ~VESTIG I CIQN y l i
fST UOI CS H ~ ~ojz 1 DO S eft
I. P. N.
BI B LICT E C A
INGENIERIA ELECTRICA
A mis padres
:Jauin (])tuz (j)iru.Ja
cf?<1£!U£{ 'Jfom cf?odtC:JUU
A quienes debo todo Ia que soy y Ia que tengo.
CUTfte 0[ INVE STIG>CIU y U
£ST UOi0::; J V,O(lt 90S f)[l
I. P. N .
B I B L I OTEC A
111/GENIE RIA ELECTil iCA
A mis hermanos
'37.anciieo :JaLrie7.
(j)ahida cf?<li!uE[
cRuGin d?ad
AIM. C.
Por su brillante y acertada direccidn de este trabajo.
CfKU& D£ IHV[STIG~ C itN y t i
[ ST UDIOS ~. ;· ,~...,z~O O$ e [l
I. P. N.
!IIB L I O T EC A
INGENIERIA ELECT!! JCA
A todos los Maestros y Alumnos de Ia Secci6n
de Computaci6n.
c:.tudia1 1in pw1a~ .e1 tan inutiL'
como p.en1a1 1in t:1tudia1.
Confucio.
cfVo impo1ta cuaft:1 1t:an foi U1uftado1, 1it:mp~t:
ha.G.ra. afguiw an1io10 po~ mafinu~p~da1fo1.
Fingles.
CUT~& 0£ IHVfSTIGACION y 1;
f STUttrOS .~ ·l'.l!d~~ OS eH
I. P. N.
BIB I_ I ()Te.: c
,..
'"JGENIERIA ELEC TRIC~
RESUMEN
Se presenta un metoda simple y eficiente para realizar
operaciones booleanas sabre s61idos representados con una
estructura de datos basada en aristas. El procedimiento divide en
tricingulos las caras de los s61idos que potencialmente se pueden
intersectar entre si. La parte esencial del algoritmo consists en el
procesamiento de los pares de tricingulos que mutuamente se
intersectan. Con este procesamiento, se determinan
los
segmentos de recta definidos par Ia intersecci6n de las caras de
los s61idos. A dichos segmentos
llamamos Hneas de
intersecci6n.
los
Una vez obtenidas las lineas de intersecci6n, es posible
dividir las caras de los s61idos que se intersectan entre si y
clasificar los poligonos resultantes, con lo cual, Ia formaciOn de un
nuevo sOlido resulta una tarea muy sencilla de realizar.
La representaciOn del sOlido se extiende de manera que se
puede trabajar con polfgonos con hoyos.
C£NT~a Of INYES TtGAC IU y II
[STUDIOS 1\' A h Z ~ OO$ S£l
I. P. N.
B I BL.
: OTE C A
'"'GENIERIA EL ECT!liCA
CONTENIDO
INTRODUCCION..
. ........... .................. !
Objetivo ........................................... ................................................... .... 2
Soluciones actuales ............................................................................... 2
. ........................... 3
Metodologia ...
Formalismo para Ia descripci6n de algoritmos..
. ........ 5
. ......................... ............ 8
Organizac1on del trabajo ..
CAPITULO 1: Conceptos Preliminares ..
1.3.1 Estructuras jer<irquicas.. .
. ... .. 9
. ............................ 9
1.1 Definiciones ..
1.2 Esquemas de representaci6n ........................................................ 11
1.3 Estructuras de datos para almacenar un sOlido ............................ 12
. ... ............................... 12
1.3.1.1 Octrees ............................................................. 13
1.3.2 Estructuras basadas en aristas ............................... ....... 14
1.3.2.1 La estructura de datos Winged· Edge ........... . .. 15
1.4 LaDCEL .................................................... .......... .. ....... ............. 17
1.4.1 Elementos de Ia DCEL .. .......... ........ ..... ......................... 17
t .4.2 1m plantae ion de Ia DCEL ................................................. 19
1.4.3 Recorrido de Ia DCEL ..................................................... 21
1.4.4 Manejo de poligonos con hoyos .................................... . 23
. ....................... 26
t .5 Consideraciones para Ia eleccion de Ia DCEL..
CAPITULO II: Descripci6n general del algoritmo de modelado de
s61idos ..
. ........... . ............................ ........ .. .................. 27
2.1 Procesamiento lnicial..
. ....................... ........................... 27
2.2 Etapas del algoritmo ................................................... .................. 28
2.2.1 Primera etapa: Obtenci6n de las lineas de
intersecci6n ..
2.2.2 Segunda etapa: Division de las caras ..
2.2.3 Tercera etapa: Obtencion de Ia DCEL del nuevo
solido ..
. .................................... ············ ....... 28
..30
. ······································· .................. 32
CfijT.~~ 0! INVES TIGAC IO~ v N.
t.STU)ICS .t YA;, z , 005 "H
I. P. N.
I B L_ ! C! T E C A.
B
l N Gf NIE RIA El Frnw· a
CAPITULO Ill: Primera etapa: Obtenci6n de las lineas de
intersecci6n ..
3.1 DivisiOn de un poligono en tricingulos ..
. .......................... 33
. ..... ..... 33
3.1.1 Obtenci6n de Ia ecuaci6n del plano definido par tres
..
~
~00
3.1.2 DeterminaciOn de Ia concavidad I convexidad de un
~~. .
3. 1.3 Algoritmo de triangulaci6n..
3. 1.4 Clasificaci6n de aristas..
.. .................................. 36
.. .................................... 37
. ....... .. 37
3.2 Prueba de intersecci6n entre dos tri8.ngulos..
3.3 Obtenci6n de una lfnea de intersecci6n .. . ..................... ............... 38
3.3.1 C8.1culo del punta de intersecci6n inicial .......................... 38
3.3.2 Algoritmo de seguimiento de triangulos ........................... 39
.. ~
3.4 Orientaci6n de las llneas de intersecci6n asociadas a una
~rn.
.. ... .40
3.4.1 Prueba de Ia orientaci6n de dos aristas ........................ .. 41
. .. ....... 43
3.4.2 Orientaci6n de aristas en sentido anti-horario..
CAPITULO IV: Segunda etapa: Division de las caras .............................. .47
4.1 Eliminaci6n de las lfneas de intersecci6n innecesarias ............... . .47
4.2 Prueba de intersecci6n entre dos segmentos de recta que se
encuentran sabre el mismo plano ........... ................................. ...... .48
4.3 Algoritmo de division ..
.. ........................................... 50
4.3.1 Eleccion de Ia primera arista ........................................... 50
4.3.2 Recorrido de aristas y Hneas de intersecci6n ...... ........... 50
4.3.3 Generacion de poligonos con hoyos .............................. 53
4.3.4 Casos en que nose divide una cara ............................... 54
.. ....... ....... ............ 55
4.4 Clasificacion de poligonos..
CAPITULO V: Tercera etapa: Obtenci6n de Ia DCEL del nuevo
objeto..
.. .............................. .................... 57
5.1 Reglas para determinar que polfgonos pertencen al nuevo
objeto..
. ....................................................... 57
5.2 Caras que tam bien pertencen al nuevo solido .............................. 58
5.2.1 Caso UNION ..
. ................... .. 58
5.2.2 Caso INTERSECCION ................................................... 59
5.2.3 Case OIFERENCIA ..
. ..... . 60
5.3 Generaci6n de Ia nueva DCEL ...................................................... 61
5.3. 1 Estructuras de datos auxiliares para almacenar
vertices, aristas y pollgonos..
··········· ........................ ........ 61
5.3.2 Numeraci6n de poligonos .................... ................. .... .... 65
5.3.3 Numeraci6n de aristas y vertices ......... .......................... 65
5.3.4 Construcci6n de Ia DCEL ... .. .............. ................... .... 69
5.3.4.1 Generaci6n de los campos A1 y A2 de Ia
oca...
5.3.4.2 Eliminaci6n de las aristas no·necesarias ........... 71
5.3.4.3 Escritura de Ia DCEL a un archive ..................... 74
··························•
CAPITULO VI: Ejemplos de s61idos generados y conclusiones
finales .......................................................................................................... .. 76
6.1 Ejemplos ..
. .... .......... 76
6.2 Caracteristicas de Ia implantaci6n .................................................. 78
. .... 81
6.3 Conclusiones finales..
APENDICE A: Generaci6n de s61idos de revoluci6n .......... ....... ................ 103
A 1 Metoda general de generaci6n de so lidos de revoluci6n . ............. 1 03
A2 Casas especiales..
. ................................................................ 111
A.2.1 La esfera ..
. ................................................................... 1 f1
A.2.2 El cone ........................................................................... 112
A.2.3 El cilindro .......................................................................... 113
A.3 Casas en que no se aplica el metoda general ............................. 113
A.4 Generaci6n del toroide .. ..................
Comentarios de: Tesis: Marco Perez - IMPLANTACION DE OPERACIONES BOOLEANAS SOBRE SOLIDOS REPRESENT ADOS CON UNA ESTRUCTURA BASADA EN ARISTAS (0)
No hay comentarios