2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
36 ** Author: Eric Veach, July 1994.
49 static GLUvertex
*allocVertex()
51 return (GLUvertex
*)memAlloc( sizeof( GLUvertex
));
54 static GLUface
*allocFace()
56 return (GLUface
*)memAlloc( sizeof( GLUface
));
59 /************************ Utility Routines ************************/
61 /* Allocate and free half-edges in pairs for efficiency.
62 * The *only* place that should use this fact is allocation/free.
64 typedef struct { GLUhalfEdge e
, eSym
; } EdgePair
;
66 /* MakeEdge creates a new pair of half-edges which form their own loop.
67 * No vertex or face structures are allocated, but these must be assigned
68 * before the current edge operation is completed.
70 static GLUhalfEdge
*MakeEdge( GLUhalfEdge
*eNext
)
75 EdgePair
*pair
= (EdgePair
*)memAlloc( sizeof( EdgePair
));
76 if (pair
== NULL
) return NULL
;
81 /* Make sure eNext points to the first edge of the edge pair */
82 if( eNext
->Sym
< eNext
) { eNext
= eNext
->Sym
; }
84 /* Insert in circular doubly-linked list before eNext.
85 * Note that the prev pointer is stored in Sym->next.
87 ePrev
= eNext
->Sym
->next
;
91 eNext
->Sym
->next
= eSym
;
99 e
->activeRegion
= NULL
;
107 eSym
->activeRegion
= NULL
;
112 /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the
113 * CS348a notes (see mesh.h). Basically it modifies the mesh so that
114 * a->Onext and b->Onext are exchanged. This can have various effects
115 * depending on whether a and b belong to different face or vertex rings.
116 * For more explanation see __gl_meshSplice() below.
118 static void Splice( GLUhalfEdge
*a
, GLUhalfEdge
*b
)
120 GLUhalfEdge
*aOnext
= a
->Onext
;
121 GLUhalfEdge
*bOnext
= b
->Onext
;
123 aOnext
->Sym
->Lnext
= b
;
124 bOnext
->Sym
->Lnext
= a
;
129 /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the
130 * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives
131 * a place to insert the new vertex in the global vertex list. We insert
132 * the new vertex *before* vNext so that algorithms which walk the vertex
133 * list will not see the newly created vertices.
135 static void MakeVertex( GLUvertex
*newVertex
,
136 GLUhalfEdge
*eOrig
, GLUvertex
*vNext
)
140 GLUvertex
*vNew
= newVertex
;
142 assert(vNew
!= NULL
);
144 /* insert in circular doubly-linked list before vNext */
151 vNew
->anEdge
= eOrig
;
153 /* leave coords, s, t undefined */
155 /* fix other edges on this vertex loop */
160 } while( e
!= eOrig
);
163 /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left
164 * face of all edges in the face loop to which eOrig belongs. "fNext" gives
165 * a place to insert the new face in the global face list. We insert
166 * the new face *before* fNext so that algorithms which walk the face
167 * list will not see the newly created faces.
169 static void MakeFace( GLUface
*newFace
, GLUhalfEdge
*eOrig
, GLUface
*fNext
)
173 GLUface
*fNew
= newFace
;
175 assert(fNew
!= NULL
);
177 /* insert in circular doubly-linked list before fNext */
184 fNew
->anEdge
= eOrig
;
187 fNew
->marked
= FALSE
;
189 /* The new face is marked "inside" if the old one was. This is a
190 * convenience for the common case where a face has been split in two.
192 fNew
->inside
= fNext
->inside
;
194 /* fix other edges on this face loop */
199 } while( e
!= eOrig
);
202 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
203 * and removes from the global edge list.
205 static void KillEdge( GLUhalfEdge
*eDel
)
207 GLUhalfEdge
*ePrev
, *eNext
;
209 /* Half-edges are allocated in pairs, see EdgePair above */
210 if( eDel
->Sym
< eDel
) { eDel
= eDel
->Sym
; }
212 /* delete from circular doubly-linked list */
214 ePrev
= eDel
->Sym
->next
;
215 eNext
->Sym
->next
= ePrev
;
216 ePrev
->Sym
->next
= eNext
;
222 /* KillVertex( vDel ) destroys a vertex and removes it from the global
223 * vertex list. It updates the vertex loop to point to a given new vertex.
225 static void KillVertex( GLUvertex
*vDel
, GLUvertex
*newOrg
)
227 GLUhalfEdge
*e
, *eStart
= vDel
->anEdge
;
228 GLUvertex
*vPrev
, *vNext
;
230 /* change the origin of all affected edges */
235 } while( e
!= eStart
);
237 /* delete from circular doubly-linked list */
246 /* KillFace( fDel ) destroys a face and removes it from the global face
247 * list. It updates the face loop to point to a given new face.
249 static void KillFace( GLUface
*fDel
, GLUface
*newLface
)
251 GLUhalfEdge
*e
, *eStart
= fDel
->anEdge
;
252 GLUface
*fPrev
, *fNext
;
254 /* change the left face of all affected edges */
259 } while( e
!= eStart
);
261 /* delete from circular doubly-linked list */
271 /****************** Basic Edge Operations **********************/
273 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face).
274 * The loop consists of the two new half-edges.
276 GLUhalfEdge
*__gl_meshMakeEdge( GLUmesh
*mesh
)
278 GLUvertex
*newVertex1
= allocVertex();
279 GLUvertex
*newVertex2
= allocVertex();
280 GLUface
*newFace
= allocFace();
283 /* if any one is null then all get freed */
284 if (newVertex1
== NULL
|| newVertex2
== NULL
|| newFace
== NULL
) {
285 if (newVertex1
!= NULL
) memFree(newVertex1
);
286 if (newVertex2
!= NULL
) memFree(newVertex2
);
287 if (newFace
!= NULL
) memFree(newFace
);
291 e
= MakeEdge( &mesh
->eHead
);
292 if (e
== NULL
) return NULL
;
294 MakeVertex( newVertex1
, e
, &mesh
->vHead
);
295 MakeVertex( newVertex2
, e
->Sym
, &mesh
->vHead
);
296 MakeFace( newFace
, e
, &mesh
->fHead
);
301 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
302 * mesh connectivity and topology. It changes the mesh so that
303 * eOrg->Onext <- OLD( eDst->Onext )
304 * eDst->Onext <- OLD( eOrg->Onext )
305 * where OLD(...) means the value before the meshSplice operation.
307 * This can have two effects on the vertex structure:
308 * - if eOrg->Org != eDst->Org, the two vertices are merged together
309 * - if eOrg->Org == eDst->Org, the origin is split into two vertices
310 * In both cases, eDst->Org is changed and eOrg->Org is untouched.
312 * Similarly (and independently) for the face structure,
313 * - if eOrg->Lface == eDst->Lface, one loop is split into two
314 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
315 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
317 * Some special cases:
318 * If eDst == eOrg, the operation has no effect.
319 * If eDst == eOrg->Lnext, the new face will have a single edge.
320 * If eDst == eOrg->Lprev, the old face will have a single edge.
321 * If eDst == eOrg->Onext, the new vertex will have a single edge.
322 * If eDst == eOrg->Oprev, the old vertex will have a single edge.
324 int __gl_meshSplice( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
326 int joiningLoops
= FALSE
;
327 int joiningVertices
= FALSE
;
329 if( eOrg
== eDst
) return 1;
331 if( eDst
->Org
!= eOrg
->Org
) {
332 /* We are merging two disjoint vertices -- destroy eDst->Org */
333 joiningVertices
= TRUE
;
334 KillVertex( eDst
->Org
, eOrg
->Org
);
336 if( eDst
->Lface
!= eOrg
->Lface
) {
337 /* We are connecting two disjoint loops -- destroy eDst->Lface */
339 KillFace( eDst
->Lface
, eOrg
->Lface
);
342 /* Change the edge structure */
343 Splice( eDst
, eOrg
);
345 if( ! joiningVertices
) {
346 GLUvertex
*newVertex
= allocVertex();
347 if (newVertex
== NULL
) return 0;
349 /* We split one vertex into two -- the new vertex is eDst->Org.
350 * Make sure the old vertex points to a valid half-edge.
352 MakeVertex( newVertex
, eDst
, eOrg
->Org
);
353 eOrg
->Org
->anEdge
= eOrg
;
355 if( ! joiningLoops
) {
356 GLUface
*newFace
= allocFace();
357 if (newFace
== NULL
) return 0;
359 /* We split one loop into two -- the new loop is eDst->Lface.
360 * Make sure the old face points to a valid half-edge.
362 MakeFace( newFace
, eDst
, eOrg
->Lface
);
363 eOrg
->Lface
->anEdge
= eOrg
;
370 /* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
371 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
372 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
373 * the newly created loop will contain eDel->Dst. If the deletion of eDel
374 * would create isolated vertices, those are deleted as well.
376 * This function could be implemented as two calls to __gl_meshSplice
377 * plus a few calls to memFree, but this would allocate and delete
378 * unnecessary vertices and faces.
380 int __gl_meshDelete( GLUhalfEdge
*eDel
)
382 GLUhalfEdge
*eDelSym
= eDel
->Sym
;
383 int joiningLoops
= FALSE
;
385 /* First step: disconnect the origin vertex eDel->Org. We make all
386 * changes to get a consistent mesh in this "intermediate" state.
388 if( eDel
->Lface
!= eDel
->Rface
) {
389 /* We are joining two loops into one -- remove the left face */
391 KillFace( eDel
->Lface
, eDel
->Rface
);
394 if( eDel
->Onext
== eDel
) {
395 KillVertex( eDel
->Org
, NULL
);
397 /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
398 eDel
->Rface
->anEdge
= eDel
->Oprev
;
399 eDel
->Org
->anEdge
= eDel
->Onext
;
401 Splice( eDel
, eDel
->Oprev
);
402 if( ! joiningLoops
) {
403 GLUface
*newFace
= allocFace();
404 if (newFace
== NULL
) return 0;
406 /* We are splitting one loop into two -- create a new loop for eDel. */
407 MakeFace( newFace
, eDel
, eDel
->Lface
);
411 /* Claim: the mesh is now in a consistent state, except that eDel->Org
412 * may have been deleted. Now we disconnect eDel->Dst.
414 if( eDelSym
->Onext
== eDelSym
) {
415 KillVertex( eDelSym
->Org
, NULL
);
416 KillFace( eDelSym
->Lface
, NULL
);
418 /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
419 eDel
->Lface
->anEdge
= eDelSym
->Oprev
;
420 eDelSym
->Org
->anEdge
= eDelSym
->Onext
;
421 Splice( eDelSym
, eDelSym
->Oprev
);
424 /* Any isolated vertices or faces have already been freed. */
431 /******************** Other Edge Operations **********************/
433 /* All these routines can be implemented with the basic edge
434 * operations above. They are provided for convenience and efficiency.
438 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
439 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
440 * eOrg and eNew will have the same left face.
442 GLUhalfEdge
*__gl_meshAddEdgeVertex( GLUhalfEdge
*eOrg
)
444 GLUhalfEdge
*eNewSym
;
445 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
446 if (eNew
== NULL
) return NULL
;
450 /* Connect the new edge appropriately */
451 Splice( eNew
, eOrg
->Lnext
);
453 /* Set the vertex and face information */
454 eNew
->Org
= eOrg
->Dst
;
456 GLUvertex
*newVertex
= allocVertex();
457 if (newVertex
== NULL
) return NULL
;
459 MakeVertex( newVertex
, eNewSym
, eNew
->Org
);
461 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
467 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
468 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
469 * eOrg and eNew will have the same left face.
471 GLUhalfEdge
*__gl_meshSplitEdge( GLUhalfEdge
*eOrg
)
474 GLUhalfEdge
*tempHalfEdge
= __gl_meshAddEdgeVertex( eOrg
);
475 if (tempHalfEdge
== NULL
) return NULL
;
477 eNew
= tempHalfEdge
->Sym
;
479 /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
480 Splice( eOrg
->Sym
, eOrg
->Sym
->Oprev
);
481 Splice( eOrg
->Sym
, eNew
);
483 /* Set the vertex and face information */
484 eOrg
->Dst
= eNew
->Org
;
485 eNew
->Dst
->anEdge
= eNew
->Sym
; /* may have pointed to eOrg->Sym */
486 eNew
->Rface
= eOrg
->Rface
;
487 eNew
->winding
= eOrg
->winding
; /* copy old winding information */
488 eNew
->Sym
->winding
= eOrg
->Sym
->winding
;
494 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
495 * to eDst->Org, and returns the corresponding half-edge eNew.
496 * If eOrg->Lface == eDst->Lface, this splits one loop into two,
497 * and the newly created loop is eNew->Lface. Otherwise, two disjoint
498 * loops are merged into one, and the loop eDst->Lface is destroyed.
500 * If (eOrg == eDst), the new face will have only two edges.
501 * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
502 * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
504 GLUhalfEdge
*__gl_meshConnect( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
506 GLUhalfEdge
*eNewSym
;
507 int joiningLoops
= FALSE
;
508 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
509 if (eNew
== NULL
) return NULL
;
513 if( eDst
->Lface
!= eOrg
->Lface
) {
514 /* We are connecting two disjoint loops -- destroy eDst->Lface */
516 KillFace( eDst
->Lface
, eOrg
->Lface
);
519 /* Connect the new edge appropriately */
520 Splice( eNew
, eOrg
->Lnext
);
521 Splice( eNewSym
, eDst
);
523 /* Set the vertex and face information */
524 eNew
->Org
= eOrg
->Dst
;
525 eNewSym
->Org
= eDst
->Org
;
526 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
528 /* Make sure the old face points to a valid half-edge */
529 eOrg
->Lface
->anEdge
= eNewSym
;
531 if( ! joiningLoops
) {
532 GLUface
*newFace
= allocFace();
533 if (newFace
== NULL
) return NULL
;
535 /* We split one loop into two -- the new loop is eNew->Lface */
536 MakeFace( newFace
, eNew
, eOrg
->Lface
);
542 /******************** Other Operations **********************/
544 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the
545 * global face list. All edges of fZap will have a NULL pointer as their
546 * left face. Any edges which also have a NULL pointer as their right face
547 * are deleted entirely (along with any isolated vertices this produces).
548 * An entire mesh can be deleted by zapping its faces, one at a time,
549 * in any order. Zapped faces cannot be used in further mesh operations!
551 void __gl_meshZapFace( GLUface
*fZap
)
553 GLUhalfEdge
*eStart
= fZap
->anEdge
;
554 GLUhalfEdge
*e
, *eNext
, *eSym
;
555 GLUface
*fPrev
, *fNext
;
557 /* walk around face, deleting edges whose right face is also NULL */
558 eNext
= eStart
->Lnext
;
564 if( e
->Rface
== NULL
) {
565 /* delete the edge -- see __gl_MeshDelete above */
567 if( e
->Onext
== e
) {
568 KillVertex( e
->Org
, NULL
);
570 /* Make sure that e->Org points to a valid half-edge */
571 e
->Org
->anEdge
= e
->Onext
;
572 Splice( e
, e
->Oprev
);
575 if( eSym
->Onext
== eSym
) {
576 KillVertex( eSym
->Org
, NULL
);
578 /* Make sure that eSym->Org points to a valid half-edge */
579 eSym
->Org
->anEdge
= eSym
->Onext
;
580 Splice( eSym
, eSym
->Oprev
);
584 } while( e
!= eStart
);
586 /* delete from circular doubly-linked list */
596 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
597 * and no loops (what we usually call a "face").
599 GLUmesh
*__gl_meshNewMesh( void )
605 GLUmesh
*mesh
= (GLUmesh
*)memAlloc( sizeof( GLUmesh
));
613 eSym
= &mesh
->eHeadSym
;
615 v
->next
= v
->prev
= v
;
619 f
->next
= f
->prev
= f
;
633 e
->activeRegion
= NULL
;
642 eSym
->activeRegion
= NULL
;
648 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
649 * both meshes, and returns the new mesh (the old meshes are destroyed).
651 GLUmesh
*__gl_meshUnion( GLUmesh
*mesh1
, GLUmesh
*mesh2
)
653 GLUface
*f1
= &mesh1
->fHead
;
654 GLUvertex
*v1
= &mesh1
->vHead
;
655 GLUhalfEdge
*e1
= &mesh1
->eHead
;
656 GLUface
*f2
= &mesh2
->fHead
;
657 GLUvertex
*v2
= &mesh2
->vHead
;
658 GLUhalfEdge
*e2
= &mesh2
->eHead
;
660 /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
661 if( f2
->next
!= f2
) {
662 f1
->prev
->next
= f2
->next
;
663 f2
->next
->prev
= f1
->prev
;
668 if( v2
->next
!= v2
) {
669 v1
->prev
->next
= v2
->next
;
670 v2
->next
->prev
= v1
->prev
;
675 if( e2
->next
!= e2
) {
676 e1
->Sym
->next
->Sym
->next
= e2
->next
;
677 e2
->next
->Sym
->next
= e1
->Sym
->next
;
678 e2
->Sym
->next
->Sym
->next
= e1
;
679 e1
->Sym
->next
= e2
->Sym
->next
;
687 #ifdef DELETE_BY_ZAPPING
689 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
691 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
693 GLUface
*fHead
= &mesh
->fHead
;
695 while( fHead
->next
!= fHead
) {
696 __gl_meshZapFace( fHead
->next
);
698 assert( mesh
->vHead
.next
== &mesh
->vHead
);
705 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
707 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
710 GLUvertex
*v
, *vNext
;
711 GLUhalfEdge
*e
, *eNext
;
713 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= fNext
) {
718 for( v
= mesh
->vHead
.next
; v
!= &mesh
->vHead
; v
= vNext
) {
723 for( e
= mesh
->eHead
.next
; e
!= &mesh
->eHead
; e
= eNext
) {
724 /* One call frees both e and e->Sym (see EdgePair above) */
736 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
738 void __gl_meshCheckMesh( GLUmesh
*mesh
)
740 GLUface
*fHead
= &mesh
->fHead
;
741 GLUvertex
*vHead
= &mesh
->vHead
;
742 GLUhalfEdge
*eHead
= &mesh
->eHead
;
744 GLUvertex
*v
, *vPrev
;
745 GLUhalfEdge
*e
, *ePrev
;
748 for( fPrev
= fHead
; (f
= fPrev
->next
) != fHead
; fPrev
= f
) {
749 assert( f
->prev
== fPrev
);
752 assert( e
->Sym
!= e
);
753 assert( e
->Sym
->Sym
== e
);
754 assert( e
->Lnext
->Onext
->Sym
== e
);
755 assert( e
->Onext
->Sym
->Lnext
== e
);
756 assert( e
->Lface
== f
);
758 } while( e
!= f
->anEdge
);
760 assert( f
->prev
== fPrev
&& f
->anEdge
== NULL
&& f
->data
== NULL
);
763 for( vPrev
= vHead
; (v
= vPrev
->next
) != vHead
; vPrev
= v
) {
764 assert( v
->prev
== vPrev
);
767 assert( e
->Sym
!= e
);
768 assert( e
->Sym
->Sym
== e
);
769 assert( e
->Lnext
->Onext
->Sym
== e
);
770 assert( e
->Onext
->Sym
->Lnext
== e
);
771 assert( e
->Org
== v
);
773 } while( e
!= v
->anEdge
);
775 assert( v
->prev
== vPrev
&& v
->anEdge
== NULL
&& v
->data
== NULL
);
778 for( ePrev
= eHead
; (e
= ePrev
->next
) != eHead
; ePrev
= e
) {
779 assert( e
->Sym
->next
== ePrev
->Sym
);
780 assert( e
->Sym
!= e
);
781 assert( e
->Sym
->Sym
== e
);
782 assert( e
->Org
!= NULL
);
783 assert( e
->Dst
!= NULL
);
784 assert( e
->Lnext
->Onext
->Sym
== e
);
785 assert( e
->Onext
->Sym
->Lnext
== e
);
787 assert( e
->Sym
->next
== ePrev
->Sym
788 && e
->Sym
== &mesh
->eHeadSym
790 && e
->Org
== NULL
&& e
->Dst
== NULL
791 && e
->Lface
== NULL
&& e
->Rface
== NULL
);