о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



Ϊ֧
¾ࡡ˼
ժҪΪ⻷ӦڷȽϵǰдԵĽģԵĻϣһָ֧ΪģͣģͿΪ֮ĿƹϵʱԼΪ⻷㷨.Ƶ⻷ƽ̨YHVRPϵĽģYHVMLʵ˸ģͣYHVMLԵлʵΪ⻷㷨ҪСɳڶȣLLFԶʵΪж̬ȵ˼룬ԱΪ⻷ӦõʵʱԺʵ.иһʵ֤ģͺ㷨Ч.
ؼʡ⻷Ϊģ Сɳڶȣʵ
ͼšTP311
LANGUAGE SUPPORT OF COMPLEX BEHAVIOR
WANG Yong-Jun, WANG Yi-Jie, Li Si-Kun, and HU Shou-Ren
(Department of Computer Science,National University of Defence Technology, Changsha410073
AbstractFor the requirement of the VR application with complex behaviors and based on the analysis and comparison of some modeling languages, a language model of complex behavior is proposed, which can represent the control relations of behaviors and their time constraints. And an algorithm of virtual environment computing for complex behaviors is also proposed. YHVML, the modeling language of distributed VR software development platform YHVRP, implements the model, whose run-time environment implements the computing algorithm for complex behaviors .The least-laxity-first (LLF) strategy is adopted to schedule behaviors dynamically to ensure the real-time interactivity and fidelity of VR application. Finally, an instance shows the efficiency of the related model and algorithm.
Key wordsvirtual environment, behavior modeling, least-laxity-first, fidelity
1
Ϊģ⻷еҪɲ֣ʵĲϷչΪ˽ʵḻɵʵ⻷бֳбҪѸָӵΪǶ⻷Ϊģ⻷ı.ˣǶǿ⻷ģԵΪģҲǷǳ.
90ʼǿʼоνͨΪģͣЩΪģͲĳЩضӦ򣬵ͨΪĸṩΪĻ˿ͬΪģ.ʵϣͳ״̬ģͨõΪģͣΪϤ¼Ļص̿Կ򵥵Ϊģ.ǣΪģԽͨã⻷ʵ彨ģ֧־͸Ч.ˣȡ߲ΪΪоΪһͨ.ⷽĵʹSunĻڹϵΪģͣ1.
ΪģֻǶΪʾĳҪоΪģͲЧͨϵͳʵֵķ.רΪģͨо߲רõʵַǰʵƽ̨Уṩģֶ֧ʵΪģЩģԶĳͨΪģ͵ʵ.
ʵƽ̨Ϊģְ֧棺һԵıʾһʵֵл֧.Եıʾܽض帴Ϊִ֮йϵΪִеʱԼлָ֧ԳԺܱϵ֧.ʵԣͨҪܶж̬޸ĺͿԭͿʵϵͳܵʵʱԺʵеĽ.ƺʵʱҪǵ.
ѡȡMR2ݣDIVE3ݣdVS4ݣAVIARY5ݺSPLINE6ݵȼ˻CSCWķֲʽʵƽ̨ΪȽǵΪģ.1ʾ.
1

ĿMRDIVEdVSAVIARYSPLINE
ֵ֧ΪģͻڹϵΪģ״̬¼Ļص¼Ļص¼Ļص
ʹOMLtclCECLJava
ʵַʽͽͱͽ
Ϊ


ֵ֧ΪģͶԣ״̬¼ĻصȻڹϵΪģҪͼӦĽģṩΪģҪͣеϵͳԸΪĽģ.Ҳֶ֧ΪִʱԼ.ʵַʽĽǶȣҪȱиԡʹû⻷ж̬޸ģֿ֧ԭͿͬʱнϺõƽ̨.
⣬еϵͳڶԽģлַ֧涼ûṩ϶Ĺ.Ҫԭǽģֻǳ򵥵Ϊ.ϵͳܷ棬ϵͳṩĺMRṩʱAVIARYDIVEṩʵǨƻƵȣŻûȥӦÿĵЧ. 
2ΪģYHVML
2.1Ϊģ
Ĺ۵⻷ʵ.ʵΪ;ֲɣǴģ͵ĽǶȶԸΪʽϵĶ.
1. ⻷. ⻷VENʵɣɼΪ
VE={Entityii=1,,N}.
2. ʵ. ʵEntityԼΪԪ飺
Entity=EntityName, AttribSet, BehSet
УEntityNameEntity
AttribSetEntityԼϣ
BehSetEntityĸΪ.
3. . AttributeʵԼϵĳԱԼΪԪ飺
Attribute=EntityName, AttrName, AttrType,
УEntityNameAttributeʵ֣
AttrNameAttribute֣
AttrTypeAttribute.
4. Ϊ. ΪBehǵĳʱĴ򣬿ԼΪԪ飺
Beh=EntityName, BehName, BehType, TrigCond,BehBody, ConstraintTime,
УEntityBehʵ֣
BehNameBeh֣
BehTypeָBehǷɱʵãBehType(External, Internal)
TrigCondBehĴ
BehBodyBehΪ壻
ConstraintTimeʽʱԼ.
Ϊ˷УرҪԽΪΪΪ.
ΪʵΪԷΪࣺһһΪGeneralBehνһΪǶʵԽоΪ.һΪǳͻΪResolutionBehΪͻָͨʵΪλĳͻʵڶΪЭʵΪλĳͻʵΪĲЭ.ͻΪ൱ڶΪͻʱٲôҲʵ佻Ļ֧.ûʽṩͻΪķҪΪ״ֱ̬ûдṹ.ͻΪǸһΪ֮ϵĸ߼Ϊ.߿ΪĴ.
5. . TrigCondһ¼GeneralEventΪͻ¼BehCollEventɼΪ
TrigCond =GeneralEvent|BehCollEvent
6. һ¼. һ¼GeneralEventһΪĴϵͳ¼SystemDefined EventԶ¼UserDefiend Event.νϵͳ¼ʱ¼Clock EventϢ¼I/O Eventײ¼Collision EventΪ¼BehCall Event.Զ¼ҪָûóCondSetProcһжֵΪʱ¼.
7. Ϊͻ¼. Ϊͻ¼BehCollEventǳͻΪĴһΪʾΪڻԾ״̬ͻ¼.еΪͬһʵΪҲǲͬʵΪ.
8. Ϊ. ΪBehBodyͼ3ͼ4еΪִαʾṹԼΪԪ飺
BehBody =InputAttrSet,OutputAttrSet, ParameterSet,ProcessingProc
УProcessingProcΪ
ԼInputAttrSetΪʵԣ
ԼInputAttrSetΪ޸ĵʵ壨ʵ壩;
ParameterSetΪĲ.
9. Ϊ. ΪCԱдĴ̣ͨC﷨⣬жΪ״̬úSetBehState()ԼΪúPBehCall().
10. Ϊú. ΪúڶһһϵΪĵãһϵΪеʱָͬʱЩΪ.ֻеЩΪִ󣬵ǰΪżִ.úĵʽΪPBehCall(BehSet)УBehSetһϵΪļ.
Ϊúǿ˶Ϊ֮ƹϵ.
Ϊ﷨ϣΪɷΪ࣬һԭΪAtomBehΪΪӦڲαʾṹеļΪִ.һǸΪCombinedBehǵΪΪӦڲαʾṹеĸΪִ.ǳƱõΪΪΪSubBehΪΪΪΪCallerBeh.ΪΪƹϵʱϵǿûԣΪĹ.
11. Ϊ. ΪBehõΪϼΪSubBehSet(Beh)üϰΪBeh.
ԵĹܣһΪֿɻΪ3ΪٱΪPresentationBehʵԽвΪ綯ΪһֱΪνָӾȸоͨЧйԣάΡٶȡλõȣڷǱΪNonPresentationBehʵǱԽвΪ漰ԵΪۼȶʵԽвֶʵǱԽвǳ֮ΪΪSynBeh.
12. ΪʱԼ. ΪʱԼConstraintTime⻷ʵΪִеʱԼΪԪ飺
ConstraintTimeˣBeginTime,DeadLine
УʼʱBeginTimeָΪʱ㣻ʱDeadLineָΪʱ㣨msΪλ.
2.2YHVML
ǻOMLиYHVMLһƽ̨ġĽģԣ֧Ϊģ.ͬʱǶ뵽⻷ƽ̨YHVRPУָ֧⻷Ĺ.YHVMLԲ˽͵ʵַ,ΪYHVRPҪɲ,YHVMLлʵΪ⻷ģͣЧ֧⻷.
2.3ڸΪ⻷ģ
ͨΪģͣǿԽ⻷ļ㿴⻷еʵΪ.ȣ⻷Ȼʵ壺ûʵ壨UserEntityͼȾʵ壨RenderEntity.ǾضΪ.ûʵIOΪⲿȤԻû⻷ĽϢ.ͼȾʵĻΪǸûǰӵ㽫⻷ʵΪıԺⳡͨάͼʾķʽֳ.
ǵ⻷ļԿһ沽ɵģÿ沽һֿԿ3βɣ1ΣûʵIOΪ㣻2Σ㵱ǰڻԾ״̬ĳʵһʵΪ޸ӦʵԺ͹ԣ3ΣͼȾʵлΪ.ھиΪ⻷УʵΪ㽫Ϊص㣬ˣ2ε㷨øӵö.һΪ֮ڵ໥ùϵʹøΪһ沽ɣҪһϵбõΪлеִ֮󣬼Ҫɷ沽.ǽص2εһΪִ㷨.
ÿʵEntάһԾΪActiveBehTab(Ent);һΪִ㷨£
㷨1. Exec(BehBody(Beh))ʱÿBehάһִнṹ(CallerBeh,ProgramPointer,State);УCallerBehǵøΪĸΪProgramPointerǳִеָ룬StateΪ״̬.YHVMLеΪ״̬лԾֹ3.
Exec(BehBody(Beh))
Begin
ProgramPointerʼִУֱBehBody(Beh)PBehCall.
IF BehBody(Beh)ִн
THEN Beh״̬ΪֹCallerBeh״̬ΪԾԾΪ.
IF PBehCall
THEN ProgramPointerָPBehCall֮.
Beh״̬Ϊ
PBehCallеΪ״̬ΪԾԾΪ
End
ɸ㷨ԿYHVMLṩûһµĸΪ幦⣬ֵ֧ʵΪĲкʵڵΪ.
3YHVMLл⻷֧ܵ
YHVMLУṩûΪִʱ֧֣⻷Ϊʵе.ڱУǽYHVMLл⻷֧֣ܵǶʱʵе֧.
3.1⻷
⻷еҪǣʵʱԺʵ.ʵʱָ⻷Ҫ㹻Ŀ죬ʹûʵʱϷӳӵı仯ĳ仯.ף7ݽûִһĻʾ֮ʱΪ˶ӳ٣EndEndLag.
ض壺
13. 沽ӳ. ⻷ڷ沽stķ沽ӳSimuStepLag ɼΪ
SimuStepLag (st)=InputLag(st)+SimuLag(st)+RenderLag(st)
УInputLag(st)ûʵIOΪʱӳ٣
SimuLag(st)һʵΪʱӳ٣
RenderLag(st)ͼȾʵΪʱӳ.
14. ˶ӳ. ⻷ڷ沽stĶ˶ӳEndEndLagɼΪ

УMûʵIOΪӦ⻷״̬ı仯ͼȾʵȾΪбִķ沽.
15. ⻷ʵʱֵ. ڲͬӦãʵʱԵͬǼ⻷ʵʱֵΪģ⻷Ķ˶ӳEndEndLag<ģ⻷ʵʱ.
3.2Ϊʵ
⻷ʵΪʵ棺 ȶ֡٣ ʵΪʱʵ.
3.2.1ȶ֡
⻷ĸ߶ȶ̬ԣ⻷ķ沽еһʵΪͼȾʵĻƼѵʱǶ̬仯ģ֡ٵĲ㶨.ף8ָ仯֡ʹ޷Ԥ⻷ٶȣ޷⻷ЧĽ֡ٵĺ㶨⻷ʵǷǳҪ.⣬ֺ㶨֡ٽûʱʱİ.
Ϊ⻷У߸ӼΪʹʵ壬һʵΪ㸺ر仯ϴ󣬺޶ִ.⣬ͼӲĲϷչȾΪļȽͣʹһʵΪΪµƿˣΪ˺㶨֡٣ֻ̬Ϊ޶Ϊʱ䣬ʹһΪļʱȾΪʱ֮Ͳᳬ㶨֡Ҫʱ䣬õڶַͨ֡彻ʱķﵽȶ֡ٵĿ.
16. ͼλʵĻΪִʱӳ. ǼͼλʵĻΪִʱΪTr沽stRenderLag(st)<Tr.
17. 㶨֡ٵķ沽ʱӳ. Ǽʹ֡ٺ㶨ķ沽ʱӳΪ.⻷㣬ÿһ沽ʱԼ£
Լ1沽stSimuStepLag(st)<.
Լ2˶ӳķ沽M</.
Լ3沽stSimuLag (st)<-Tr.ǺûʵIOΪʱӳInputLag(st).
3.2.2ʵΪʱʵ
ʵÿΪԼʱԼ.ͨΪڶ沽мֱ.
18. Ϊʵִʱ. ΪBehʵִʱActualExecTimeԼΪ
ActualExecTime(Beh)BehCompLen(Beh)
УBehCompLenBehʵʵļ沽.
ΪΪʱʵУԼ4
Լ4ΪBehDeadLine(Beh)>ActualExecTime(Beh).
3.3ΪʵΪ̬Ȳ
3.3.1˼
⻷ʵܴΪļҲܴʱάÿΪʱԼܴ޷ÿһ沽ʵΪʱԼ֡ٵ½ʵʱܵ½ƻ⻷ʵ.ˣҪĳЩʵΪִʱ䣬ĳЩΪӳٵķ沽УӶʹõǰ沽Լ3.
⻷߶ȶ̬ԣֻ̬ͨȲſ⻷Ҫ.㷨ͨΪԤķжϵǰ沽һʵΪSimuLagǷ񳬹ޣǣ͸ԭѡȼߵΪƳٵһ沽ִУֱǰ沽Լ3.
ԭ1.ڱΪͻΪͬҪϸߣˣǱΪȼΪȼߣ
ԭ2.ͬΪУѭСɳڶȣleast laxity firstLLF[9]㷨˼룬ɳڶȴΪȼߣ
3.3.2ɳڶȶ
19. Ϊִʱ. ΪBehڷ沽stִʱBehFinishedCompTime(Beh, st)ΪΪѱִеķ沽.
20. Ϊִ. ΪBehڷ沽stִBehFinishedCompLen (Beh, st)ΪΪѱִеķ沽.
21. Ϊɳڶ. ΪBehڷ沽stɳڶLaxity(Beh, st)ָȥΪִķ沽ΪʱԼľ룬
Laxity(Beh, st)=DeadLine(Beh)-BehFinishedCompTime(Beh, st)-á(BehCompLen(Beh)-BehFinishedCompLen (Beh, st))
4Ӧʵ
YHVMLдһ⻷ϵͳвԣҪһģͽΪ򵥵agent3ΪǱΪrunwagtailһǻΪthink.runһάռƶthinkǽһݼϵÿɹwagtailҡβ.
Ӳǣ PC586120MHzƵ32MBڴ棬S3 64V+ͼμٿ.
ӲӦʵ趨ز£
⻷ʵʱֵΪģ100ms,
֡ٺ㶨ķ沽ʱӳΪã100ms;
ͼλʵĻΪִʱΪTr30ms;
һʵΪִʱΪ-Tr70ms;
һʵΪӳMaxSimuLag70ms
ã⻷agentʵmike1mike2ǶӵһΪrunһΪthink.
LLFԵĸΪ̬ʱ mike1mike2ͼ1ʾ.ʵ⻷е֡ٵڦõ֡ﵽ20%.


ͼ1δΪ̬ʱ
LLFԵĸΪ̬ʱmike1mike2ͼ2ʾͼпԿthinkΪʱڸΪ̬Ԥ⵱ǰ沽SimuLagMaxSimuLag˽һthinkΪͺһ沽ִУȶ֡ٵĴʩʹ⻷沽ӳά100ms.ʵ⻷֡ٵڦõ֡͵10%.


ͼ2Ϊ̬ʱ
5ᡡ
Ϊģ͵ʵӦãһָ֧Ϊģͣģ;кǿΪʱ.Ƶ⻷ƽ̨YHVRPĽģYHVMLʵ˸ģͣԵлϺõ֧ΪʱԼΪʵӦõʵʱԺʵ.
߼飺¾У19712ʿоԱҪоΪʵͲзֲ.࣬Ů19719ʿоΪݿͲзֲ.˼У19414ڣʿʦоΪCADʵ.ʣУ19269ڣʿʦҪоΪܻϵṹзֲ.
ߵλѧѧѧϵɳ410073
ο
1Sun H. A relation model for animating adaptive behavior in dynamic environments.University of Alberta,1992
2Shaw C,Green M et al. Decoupled Simulation in virtual reality with the MR toolkit. ACM Trans on Information Systems, 1993, 11(3):287317
3Hagsand O.Interactive multiuser VES in the DIVE System.IEEE Multimedia,1996,3(1):3039
4Division dVS v2.04 Technical Overview.London:Division Lt, 1992
5Snowdon D N. AVIARY:Design issues for future large-scale virtual environments. Presence:Teleoperators and Virtual Environments,1994,3(4):220241
6Barrus J W, Waters R C, Anderson D B. Locals: Supporting large multiuser virtual environments. IEEE Computer Graphics and Applications,1996,16(6):505
7 7Wloka M M.Lag in multiprocessor virtual reality.Presence:Teleoperators and Virtual Environments,1995,4(1):5063
8Hawkes R et al. Update rates and fidelity in virtual environments. Virtual Reality,1995,1(2):99108
9Cheng S. Scheduling algorithms for hard real-time systemsA brief survey. In:Stankovic J A,Ramamrithan K eds.Hard Real-Time Systems.New York:Academic Press,1988
ԭյڣ1998-04-08
޸ĸյڣ1999-01-19
