PDF de programación - Tesis: Marco Perez - IMPLANTACION DE OPERACIONES BOOLEANAS SOBRE SOLIDOS REPRESENT ADOS CON UNA ESTRUCTURA BASADA EN ARISTAS

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 .. ..................